Метод для решения систем линейных уравнений был разработан Ф. Гауссом (года жизни 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