Метод Гаусса с выбором главного элемента (метод последовательного исключения неизвестных)

 

Процесс решения системы уравнений методом Гаусса делится на два этапа. На первом этапе (прямой ход) последовательным исключением неизвестных составляется преобразованная, эквивалентная система уравнений с треугольной матрицей, в которой все элементы под главной диагональю равны нулю. При этом одно из уравнений в системе содержит только одну неизвестную, а в каждом следующем - добавляется еще по одной неизвестной. На втором этапе (обратный ход) решается преобразованная система уравнений.

 

6.2.1 Алгоритм метода Гаусса

Прямой ход:

а) среди элементов матрицы А а_ij, i,j=1…n выбирается наибольший по модулю а_pq называемый главным элементом. Соответственно строка с этим элементом будет главной строкой. Предположим, что а_pq=a₁₁, если это не так, то меняют местами первую строку со строкой p и первый столбец со столбцом q, при этом совершают перенумерацию коэффициентов и неизвестных. Информацию о перенумерации необходимо запомнить. Теперь первая строка становится главной;

б) полученное первое уравнение системы делится на a₁₁ = a_pq и получают уравнение вида:

x₁+c₁₂x₂+… +c_1nx_n=d₁, (6.7)

где c_ij=a_1j/a₁₁, d₁=b₁/a₁₁, j=2…n;

в) исключают, неизвестную величину х₁ из каждого уравнения исходной системы начиная со второго, путем вычитания уравнения шага б), умноженного на коэффициент а_i1, при х₁ в соответствующем уравнении. Отбрасывают главную строку и первый столбец матрицы А и получают преобразованную систему уравнений:

c₂₂x₂+c₂₃x₃+… +c_2nx_n=d₂

...................., (6.8)

c_n2x₂+c_n3x₃+… +c_nnx_n=d_n

 

где c_ij=a_ij-c_ija_i1, d_i=b_i-d_ia_i1; (6.9)

г) над системой шага в) (6.8) повторяют операции шагов а) - в), в результате чего получают систему уравнений, содержащих неизвестные х₃… х_n. Такие преобразования продолжают до тех пор, пока не получат одно уравнение с одним неизвестным:

c_nnx_n=d_n (6.10)

Это уравнение также считают главным.

д) объединяют все главные уравнения и получают систему с треугольной матрицей, эквивалентную исходной:

x₁+c₁₂x₂+c₁₃x₃+… +c_1nx_n=d₁

c₂₂x₂+c₂₃x₃+… +c_2nx_n=d₂

c₃₃x₃+… +c_3nx_n=d₃ (6.11)

.............

c_nnx_n=d_n

 

Обратный ход.

Из системы шага д) (6.11) неизвестные определяются в обратном порядке:

x_n=d_n/c_nn

x_n-1=d_n-1-c_n-1x_n

.............. (6.12)

x₁=d₁-c₁₂x₂-c₁₃x₃-… -c_1nx_n

 

В случае вырожденной матрицы с_nn= 0, получить х_n невозможно -метод Гаусса неприменим.

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

 

Метод Зейделя

 

Суть итерационного метода Зейделя состоит в том, что задается некоторый произвольный вектор х [0], являющийся началом приближения к искомому решению х*. Затем строят последовательность приближенных значений {x[k]}, где k=0,1,2,…, сходящихся к х*

lim x[k]=x*, при k→∞.

Последовательность векторов х[0], x[1], …, x[k] сходится к х* в том случае, если для любого ε > 0 существует натуральное число N, начиная с которого (k ≥ N), выполняется условие

||x*-x[k]|| < ε,

где ||·|| - норма вектора.

 

6.3.1 Алгоритм метода Зейделя

А) Исходную систему линейных алгебраических уравнений

x₁+c₁₂x₂+c₁₃x₃+… +c_1nx_n=d₁

x₂+c₂₁x₁+c₂₃x₃+… +c_2nx_n=d₂

...................... (6.13)

c_n1x₁+c_n2x₂+c_n3x₃+… +x_n=d_n

разрешают относительно неизвестных х₁, х₂, …, х_n и приводят к виду:

x₁=c₁₂x₂+… +c_1nx_n+d₁

x₂=c₂₁x₁+… +c_2nx_n+d₂ (6.14)

..................

x_n=c_n1x₁+… +c_nnx_n+d_n

Такое преобразование всегда можно выполнить, если определитель системы отличен от нуля.

Б) Задают начальные значения вектора x[0]={x₁[0], x₂[0], …, x_n[0]}. Начальный вектор может быть выбран произвольно, однако необходимо использовать всю информацию, чтобы вектор x[0] был близок к х*.

В) В первое уравнение системы (6.14) подставляют координаты точки x[0] и вычисляют значение первой координаты:

x₁[1]=c₁₂x₂[0]+c₁₃x₃[0]+… +c_1nx_n[0]+d₁.

В следующее уравнение подставляем х₁[1] и значения x_n[0]:

х₂[1]=c₂₁x₁[1]+c₂₃x₃[0]+… +c_2nx_n[0]+d₂.

Аналогично для x_n[1]:

x_n[1]=c_n1x₁[1]+c_n2x₂[1]+… +d_n

В результате будет найдено

x[1]={x₁[1],…,x_n[1]}.

Г) Начальный вектор x[0] заменяют x[1] и вычисляют следующее приближение. В общем случае k+1 приближение определяется по формуле:

x₁[k+1]=c₁₂x₂[k]+…+c_1nx_n[k]+d₁

x₂[k+1]=c₂₁x₁[k+1]+…+c_2nx_n[k]+d₂

...........................

x_n[k+1]=c_n1x₁[k+1]+…+d_n

Итерационный процесс будет продолжаться до тех пор, пока все x_i[k+1] не будут близки с x_i[k], то есть выполнится условие:

||x_i[k+1]-x_i[k]|| < ε, (6.15)

где ε - точность вычисления.

Можно показать, что с помощью метода Зейделя строится сходящаяся к точному решению последовательность векторов {x[k]}, если матрица А системы уравнений удовлетворяет условию:

|a_ij| > |a_i1| + |a_i2| +…+ |a_in|. (6.16)

Для всех i или хотя бы для одного i должно удовлетворятся условие:

|a_ii| > |a_i1| + |a_i2| +…+ |a_in|. (6.17)