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

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

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

Прямой ход:

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

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

x1+c12x2+… +c1nxn=d1, (6.7)

где cij=a1j/a11, d1=b1/a11, j=2…n;

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

Метод Гаусса с выбором главного элемента (метод последовательного исключения неизвестных) - student2.ru c22x2+c23x3+… +c2nxn=d2

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

cn2x2+cn3x3+… +cnnxn=dn

где cij=aij-cijai1, di=bi-diai1; (6.9)

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

cnnxn=dn (6.10)

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

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

Метод Гаусса с выбором главного элемента (метод последовательного исключения неизвестных) - student2.ru x1+c12x2+c13x3+… +c1nxn=d1

c22x2+c23x3+… +c2nxn=d2

c33x3+… +c3nxn=d3 (6.11 )

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

cnnxn=dn

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

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

xn=dn/cnn

Метод Гаусса с выбором главного элемента (метод последовательного исключения неизвестных) - student2.ru xn-1=dn-1-cn-1xn

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

x1=d1-c12x2-c13x3-… -c1nxn

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

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

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

Метод Гаусса с выбором главного элемента (метод последовательного исключения неизвестных) - student2.ru Метод Гаусса с выбором главного элемента (метод последовательного исключения неизвестных) - student2.ru Метод Гаусса с выбором главного элемента (метод последовательного исключения неизвестных) - student2.ru Суть итерационного метода Зейделя состоит в том, что задается некоторый произвольный вектор х [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 Алгоритм метода Зейделя

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

Метод Гаусса с выбором главного элемента (метод последовательного исключения неизвестных) - student2.ru x1+c12x2+c13x3+… +c1nxn=d1

x2+c21x1+c23x3+… +c2nxn=d2

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

cn1x1+cn2x2+cn3x3+… +xn=dn

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

Метод Гаусса с выбором главного элемента (метод последовательного исключения неизвестных) - student2.ru x1=c12x2+… +c1nxn+d1

x2=c21x1+… +c2nxn+d2 (6.14)

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

xn=cn1x1+… +cnnxn+dn

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

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

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

x1[1]=c12x2[0]+c13x3[0]+… +c1nxn[0]+d1.

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

х2[1]=c21x1[1]+c23x3[0]+… +c2nxn[0]+d2.

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

xn[1]=cn1x1[1]+cn2x2[1]+… +dn

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

x[1]={x1[1],…,xn[1]}.

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

Метод Гаусса с выбором главного элемента (метод последовательного исключения неизвестных) - student2.ru x1[k+1]=c12x2[k]+…+c1nxn[k]+d1

x2[k+1]=c21x1[k+1]+…+c2nxn[k]+d2

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

xn[k+1]=cn1x1[k+1]+…+dn

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

Метод Гаусса с выбором главного элемента (метод последовательного исключения неизвестных) - student2.ru ||xi[k+1]-xi[k]|| < ε, (6.15)

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

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

|aij| > |ai1| + |ai2| +…+ |ain| . (6.16)

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

|aii| > |ai1| + |ai2| +…+ |ain| . (6.17)

Наши рекомендации