Теория некоторых методов - 2003 / Решение систем линейных алгебраических уравнений

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

Все методы решения СЛАУ делятся на:

1)точные

2)итерационные

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

Итерационные методы дают некоторую последовательность приближений к решению.

Метод Гаусса

Требуется решить систему n-линейных уравнений с n неизвестными.

Метод Гаусса включает два этапа.

Первый этап (прямой ход) заключается в последовательном исключении неизвестных из системы уравнений и состоит из (n – 1) шага.

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

Второй этап (обратный ход) заключается в последовательном вычислении искомых неизвестных и состоит из n-шагов. Решая последнее уравнение, находим неизвестное . Далее используем это значение из предыдущего уравнения и вычисляем неизвестное и т.д.

Последним найдём неизвестное из первого уравнения.

Матрица, содержащая помимо коэффициентов при неизвестных столбец свободных членов , называется расширенной

Модификации метода Гаусса

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

При полном выборе в качестве ведущего элемента выбирается max по модулю элемент из всей неприведённой части матрицы коэффициентов системы:

Метод простых интераций

Алгоритм метода состоит их трёх этапов.

Первый этап. Решим каждое уравнение относительно соответствующего неизвестного:

……………………………………

, где

Тогда интегрирующую формулу запишем в виде:

, где вектор - приведённый столбец свободных членов, матрица - приведённая матрица коэффициентов.

Второй этап. Проверяем условие сходимости если условие не выполняется, то преобразуем исходную систему и выполняем первый этап.

Третий этап. Уточнение решения по полученной итерационной формуле. За начальное приближение принимается вектор

Условием окончания итерационного процесса является выполнение условия:

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

Программа решения СЛАУ методом Гаусса

Option Explicit

Option Base1

Sub Gausse( )

Dim n%,c!( ),x!( )

Dim i%,j%( ),k%,bet!,s!

n=cells(1,3)

Redim c(n,n+1), x(n)

For i=1 to n

For j=1 to n+1

c(i,j)=cells(i+3,j+1)

Next j

Next i

For k=1 to n-1

For i=k+1 to n

Bet=-c(i,k)/c(k,k)

For j=k to n+1

c(i.j)=c(I,j)+bet*c(k,j)

Next j

Next i

Next k

x(n)=c(n,n+1)/c(n,n)

For i=n-1 to 1 step -1

s=0

For j=i+1 to n

S=s+c(i,j)*x(i)

Next j

For j=1 to n

Cells (n+5,j)=x(j)

Next j

End Sub

Пример:

-7 -2 1 -7

-2 4 -2 4

-1 2 -6 -6

-7 - 2 1 -7

-2 4 - 2 = 4

1 2 6 6

Первый этап. Строим расширенную матрицу и преобразуем её к ступенчатому виду:

-7 -2 1 -7 -7 -7 -2 1 -7 ( ) -7 -2 1 -7

-2 4 -2 4 4 () -2 4 -2 4 0 4,6 -1,7 6

-1 2 -6 -6 -6 0 0 5 -8 0 0 5 -8

Второй этап. Вычисляем неизвестные:

Программа вычисления СЛАУ методом простых итераций

Option Explicit

Option Base1

Sub Iter( )

Dim n%,a!( ),b!( ),c!( ),x!( ),d!( )

Dim z!( ),e!( ),i%,j%( ),k%,normc!

n=cells(2,1)

Redim a(n,n), b(n),c(n,n),d(n),x(n)

For i=1 to n

For j=1 to n+1

c(i,j)=cells(i+1,j+1)

Next i

Next j

For i=1 to n

For j=1 to n

If j=1 then c(i,j)=0

Else c(i,j)=a(i,j)/a(i,j)

Cells (6+i,y+1)=c(i,j)

Rem ocenka chodimosti

Norm c=norm c+c(i,j)^2

Next j

Next i

Norm c=sqr(normc)

If norm c >1 then Msgbox «norma bolwe edinicy»

& norm c:goto 665

End If

For i=1 to n

x(i)=d(i)

Next j

Norm dx=0

Do

For i=1 to 1

cx(i)=cx(i)+c(i,j)*x(j)

Next j

z(i)=d(i)-cx(i)

dx(i)=z(i)-x(i)

norm dx=normdx+dx(i)^2

Next i

Norm dx=sqr(normdx)

For i=1 to n

x(i)=z(i)

Next i

Loop while norm dx>e

For i=1 to n

Cells (6+i,1)=z(i)

Next i

End Sub