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

 

Решим следующую СЛАУ методом Гаусса.

 

 

,

 

где a= .

Конечная разрядность компьютера предполагает неизбежные округления. Будем считать, что наш компьютер при округлении получает a»1. Поэтому обратный ход дает X₂=1, X₁=10⁴ - 10⁴ = 0, т.е. вектор решения получается

X= - неверный результат.

Переставим уравнения в исходной системе местами, тогда имеем:

.

Точное решение задачи

Принципиальное отличие между этими двумя случаями заключается в том, что при перестановке уравнений ведущие элементы оказываются одного порядка, в то время как без перестановки они несопоставимы по порядкам. Именно это обстоятельство приводит к потере значащих цифр при округлении. Поэтому прямой ход в методе исключения непременно должен включать в себя стратегию выбора ведущего элемента, фиксируемого на главной диагонали. Например, в стратегии частичного упорядочивания ведущий элемент выбирается как максимальный по модулю в k -ом столбце на k -ом шаге исключения: a_kk=max½a_ik½ для k £ i £ n. Такая модификация носит название метода Гаусса с выбором максимального элемента по столбцу. Возможны также варианты выбора максимального элемента по строке и по всей матрице, но они связаны с дополнительными сложностями в реализации алгоритмов.

 

Решение систем линейных алгебраических уравнений методом прогонки.

 

Метод прогонки для решения систем с трёхдиагональной матрицей

Часто возникает необходимость в решении систем, матрицы которых, являясь слабозаполненными, т.е. содержащими много ненулевых элементов. Матрицы таких систем обычно имеют определенную структуру, среди которых выделяют системы с матрицами ленточной структуры, т.е. в них ненулевые элементы располагаются на главной диагонали и на нескольких побочных диагоналях. Для решения систем с ленточными матрицами метод Гаусса можно трансформировать в более эффективные методы.

Рассмотрим наиболее простой случай ленточных систем, к которым, как мы увидим впоследствии, сводится решение задач дискретизации краевых задач для дифференциальных уравнений методами конечных разностей, конечных элементов и др. Трёхдиагональной матрицей называется такая матрица, у которой ненулевые элементы стоят только на главной диагонали и соседних с ней:

У трёхдиагональной матрицы ненулевых элементов всего (3n-2).

Переобозначим коэффициенты матрицы:

.

Тогда в покомпонентной записи систему можно представить в виде:

a_{i *} x_i-1 + b_{i *} x_i + c_{i *} x_i+1 = d_i, i=1, 2,…, n; (7)

a₁=0, c_n=0. (8)

Структура системы предполагает взаимосвязь только между соседними неизвестными:

x_i=x_{i *}x_i+1+h_i (9)

Уменьшим в представлении (9) индекс на единицу:

x_i-1=x_i-1*x_i + h_i-1 и подставим в (7):

a_i(x_i-1*x_i + h_i-1)+ b_{i *} x_i + c_{i *} x_i+1 = d_i

(a_{i *}x_i-1 + b_i )x_i = –c_{i *} x_i+1 +d_i –a_{i *} h_i-1

Сравнивая полученное выражение с представлением (7), получаем:

(10)­

Формулы (10) представляют реккурентные соотношения для вычисления коэффициентов прогонки. Они требуют задания начальных значений. В соответствии с первым условием (8) для i =1 имеем a₁=0, а значит

, .

Далее вычисляются и сохраняются остальные прогоночные коэффициенты по формулам (10) для i=2,3,…, n, причем при i=n, с учетом второго условия (8), получаем x_n=0. Следовательно, в соответствии с формулой (9)

x_n = h_n.

После чего по формуле (9) последовательно находятся неизвестные x_n-1, x_n-2, …, x₁. Этот этап расчета называется обратным ходом, в то время как вычисление прогоночных коэффициентов называется прямым ходом прогонки.

Для успешного применения метода прогонки нужно, чтобы в процессе вычислений не возникало ситуаций с делением на нуль, а при большой размерности систем не должно быть быстрого роста погрешностей округления. Будем называть прогонку корректной, если знаменатель прогоночных коэффициентов (10) не обращается в ноль, и устойчивой, если ½x_i½<1 при всех i=1,2,…, n.

Достаточные условия корректности и устойчивости прогонки, которые во многих приложениях выполняются, определяются теоремой.

Теорема. Пусть коэффициенты a_i и c_i уравнения (7) при i=2,3,..., n-1 отличны от нуля и пусть

½b_i½>½a_i½+½c_i½ при i=1, 2,..., n. (11)

Тогда прогонка, определяемая формулами (10), (9) корректна и устойчива.

 

 

Алгоритм метода прогонки.