Вопрос 40.doc

Системы линейных алгебраических уравнений, нормы; обусловленность задачи решения линейной системы.

Норма – функция f: Rⁿ→R, обозначается , обладает следующими свойствами:

1.        ,,

2.       

3.                       1, 2, 3 – аксиомы нормы.

Чтобы доказать аксиомы нормы докажем неравенство Коши-Буняковского.

В трехмерном пространстве нормой вектора является его длина.

Док-во: рассмотрим ,

Если извлечь корень из D, то неравенство Коши-Буняковского превращается в строгое неравенство. Равенство возможно в случае, когда один из векторов равен нулю.

Неравенство треугольника.

Извлекая корень, получим неравенство треугольника.

В вычислениях применяются все три вида норм. Они применяются для оценки погрешностей. Применение различных норм неравносильно.

Норма линейного оператора.

Линейный оператор – это отображение Rⁿв R, т. е. A: Rⁿ → R. Ax=y , при

Отождествлять, что матрица соответствует оператору нельзя. Если    (*) – такой оператор называется ограниченным. Операторы, действующие в пространстве Rⁿ  ограничены.

Наименьшая из констант C, для которых для любого x из пространства Rⁿ выполняется условие (*) называется оператором.   (**)  .

Рассмотрим первую норму:

Возьмем x=(α,α,α,α,….,α), тогда первая норма x равна α, - это есть норма. Т. е.  С помощью неравенства Коши-Буняковского можно показать, что

Обусловленность задачи решения системы линейных алгебраических уравнений.

Если правая часть линейного уравнения задана с погрешностью, то и в входном параметре будет погрешность, т. е. . Систему линейных уравнений можно записать как  (1). Если , то . Подставим в систему и получим:(2). Вычтем из (2) выражение (1), тогда . Обусловленность любой задачи определяется числом обусловленности. Пусть в какой-то задаче f - совокупность входных параметров, а x – совокупность входных параметров.

  Мы должны получить оценку , где μ(A) – число обусловленности и . Начнем с правой части. Система имеет решение при любых x следовательно , тогда существует обратная матрица A^-1 и .        (согласно аксиомам норм).

. Мы доказали обусловленность для линейной системы.

Если  , тогда . Хотя детерминант мал, но норма оказалась бесконечно большим числом, следовательно μ(A) будет велико. Однако, даже если решение плохо обуславливает систему точным методом, результат может получиться далеким от истинного, значит плохо обусловленные системы надо решать другими методами.

  Рассмотрим систему с диагональным преобладанием Ax=f, , . Тогда справедлива теорема:

Система с диагональным преобладанием всегда совместна. Обратная матрица существует и .

Простой метод Гаусса и метод Гаусса с выбором главного элемента.

Процесс решения системы линейных алгебраических уравнений Ax=b,  (1), i= по методу Гаусса состоит из 2-х этапов. I этап – прямой ход: приведем систему (1) к треугольному виду. Рассмотрим систему при n=3.(2)

Пусть  – ведущий элемент. Разделим на него первое уравнение системы (2): (3), , j=2,3, . Умножим (3) на a₂₁, a₃₁ и вычтем результаты из 2-го и 3-го уравнений системы, исключив этим из них x₁. Обозначим , i,j=2,3,  и перепишем полученную систему:(4). Разделим 2-е уравнение системы (4) на :, , . Исключив x₂ (аналогично x₁) получим:  (5), , . Разделим на  третье уравнение системы (5):  (6), где .

II этап – обратный ход: он состоит в определении всех x_i из системы (6). Неизвестные x₁, x₂, x₃ определяются по формулам: .

Число арифметических операций, необходимых для реализации метода Гаусса, определяется формулой:, где n – число неизвестных.

Отличие метода Гаусса с выбором главного элемента от выше описанной схемы, состоит в следующем: пусть по ходу исключения неизвестных получена следующая система уравнений: . Найдем l, т.ч.. Произведем перестановку столбцов системы и переобозначим:    x_k+1=x_l, x_l=x_k+1. Далее произведем исключение неизвестной x_k+1 из всех уравнений, начиная с (k+2)–го. Такое переобозначение приводит к изменению порядка исключения неизвестных и во многих случаях существенно уменьшает чувствительность решения к погрешностям округления при вычислениях. К таким же перестановкам приходится прибегать, когда ведущий элемент, т.е. стоящий на главной диагонали, =0.