Метод для решения систем линейных уравнений был разработан Ф. Гауссом (года жизни 17хх-18хх). Он предназначен для облегчения решения системы линейных уравнений. И также называется прямым методом.

Этот метод используя элементарные преобразования над системой для приведения её к треугольному виду. Затем применяется метод обратной подстановки для нахождения решения.

В отличие от метода Гаусса метод Жордана-Гаусса основан не на обратной подстановке найденных значений, а на применение элементарных преобразований над и под главной диагональю.

Метод гауса Запишем нашу систему в виде матрицы. Индексы в матрице будут считаться от нуля.

Будем решать систему методом исключений, путем сведения матрицы системы к треугольной. Выполняем исключения в нулевом столбце: - Если a[0,0]=0, то найдем A[i,0]<>0 и переставим строки 0 и i местами;

- строку 0 не изменяем;

- строку 1 заменим линейной комбинацией строк: строка_1∗a[0,0]-строка_0∗a[1,0];

- строку 2 заменим линейной комбинацией строк: строка_2∗a[0,0]-строка_0∗a[2,0];

- и т.д.

Общая формула для исключения из нулевого столбца.

Строку i (i=1,…,N) заменим линейной комбинацией строк: строка_i∗a[0,0]-строка_0∗a[i,0].

Завершив исключения в столбце 0, переходим к столбцу 1 и т.д.

После исключения в столбце n − 1 мы получим систему с треугольной матрицей.

Недостаток такого подхода - большое число умножений. Для исключения одного элемента потребуется выполнить 2*n + 2 умножений (включая умножения на 0). Пожалуй стоит сказать что это самый точный метод, так как остальные подвержены округлениям.

Модифицируем метод:

Переделаем формулу (1) в (2) а затем в (3):

1) строка_i∗a[0,0]-строка_0∗a[i,0];

2) строка_i-строка_0∗a[i,0]/a[0,0];

3) строка_i-строка_0*u , где u=a[i,0]/a[0,0].

Получится следующий алгоритм.

Выполняем исключения в нулевом столбце: - Если a[0,0]=0, то найдем A[i,0]<>0 и переставим строки 0 и i местами;

- строку 0 не изменяем;

- строку 1 заменим линейной комбинацией строк: строка_1-строка_0∗u, где u=a[1,0]/a[0,0];

- строку 2 заменим линейной комбинацией строк: строка_2-строка_0∗u, где u=a[2,0]/∗a[0,0];

- и т.д.

Общая формула для исключения из нулевого столбца.

Строку i (i=1,…,N) заменим линейной комбинацией строк: строка_i-строка_0*u , где u=a[i,0]/a[0,0].

Завершив исключения в столбце 0, переходим к столбцу 1 и т.д.

Общая формула для исключения из j столбца.

строка_i-строка_j*u , где u=a[i,j]/a[j,j].

После исключения в столбце n − 1 мы получим систему с треугольной матрицей.

Заметим что число умножений для исключения одного элемента теперь сократилось в двое. И добавилось одно деление.

В наших рассуждениях мы не учили одну особенность. Дело в том что в результате после деление 1/3=0.33333(3) числа могут оказаться бесконечными. А в компьютере конечное число разрядов. Поэтому либо числа обрабатывать в рациональным представлении(в виде дроби). Либо бороться с ошибками округления.

Дальше пойдет обсуждение ошибок округления и методов борьбы с ними.

Так вот описанный выше метод имеет недостаток. В нем быстро нарастает вычислительная погрешность. Коэффициенты системы (числа вещественного типа) представляются в компьютере с некоторой погрешностью. Результаты арифметических операций над числами также получаются с некоторой погрешностью. В процессе вычислений погрешность будет возрастать. Проблемы начинаются когда в ходе вычислений коэффициенты матрицы начинают превосходить исходные значения матриц более машинной ошибки. При арифметике с плавающей точкой арифметические операции идут с округление или с усечением результата. И в ходе вычисления у нас коэффициенты будут рости, то рано или поздно мы наткнемся на то, что будет выполнятся условие (1)
1) строка_i-строка_0*u=строка_0*u
И все последующие операции уже будут неверны так, как они будут связаны только с первыми элементами и не будут учитывать вклад последующих. И исключение элементов в последующем столбце будет, только наращивать ошибку. Когда как если выполняется уравнение (2), то такой проблемы не возникает.
2) строка_i-строка_0*u=строка_i
Такая система более устойчива. Если ошибки и будут, то при исключение элементов в следующем столбце они не будут превосходить исходной ошибке матрицы(машинной ошибки).

Этого легко добиться, если abs(u) будет меньше или равно 1.
abs(u)=abs(a[i,j]/a[j,j]) < = 1

Что достигается частичным выбором главного элемента.

Ошибки округления очень сильно могут влиять на результат даже в небольшой матрице 3х3 и при небольших входных данных. Подробнее описано в [2].

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

Для того, чтобы компенсировать недостаток устойчивости, будем поступать следующим образом:

- исключение в столбце j начинаем с того, что среди элементов столбца, начиная с главной диагонали и ниже, максимальный по абсолютной величине элемент. Пусть среди A[k,j] k=j,..,n-1 мы нашли максимальный элемент A[g,j] тогда меняем местами строки j и g.

При этом у нас всегда будет выполнятся условие abs(u)=abs(a[i,j]/a[j,j]) < = 1

Элемент A[g,j] называется главным (или ведущим) элементом, метод исключения - методом Гаусса с выбором главного (ведущего) элемента.


Список литературы:

[1] В виду что пока мне не попалось внятного описания в книгах ссылаюсь на следующий документ-

www.kafit.sci.pfu.edu.ru/B_F/Lab24.doc

[2]Немного про ошибки в вычислениях и связанные с этим эффекты -
Каханер,_Моулер,_Наш.-Численные_методы_и_программное_обеспечение-Мир(1998)

[3] Гораздо подробнее и лучше чем в [1]
http://files.lib.sfu-kras.ru/ebibl/umkd/13/u_lectures.pdf

 
articles/метод_жордана-гаусса.txt · Последние изменения: 2013/05/12 15:31 От Pavia
 
Recent changes RSS feed Donate Powered by PHP Valid XHTML 1.0 Valid CSS Driven by DokuWiki