Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
Alg_Lang_All.doc
Скачиваний:
11
Добавлен:
01.07.2025
Размер:
3 Мб
Скачать
☆

Метод Гаусса-Зейделя

Для решения систем линейных уравнений наряду с прямыми методами решений (метод Гаусса) используются и итерационные методы. Одним из наиболее простых итерационных методов решения систем линейных уравнений является с метод Гаусса-Зейделя.

В соответствии с методом Гаусса-Зейделя исходную систему линейных уравнений

A*X=B, (4)

приводят к виду:

X=B-C*X, (5)

где матрица С=А-Е, Е–единичная матрица.

Аналогичное преобразование используется при нахождении корня нелинейного уравнения методом простой итерации.

Алгоритм метода Гаусса-Зейделя состоит в следующем: на первом этапе задается начальное приближение вектора X (либо его первая компонента), далее по формуле (5) вычисляется новое улучшенное значение X. Итерации повторяются до тех пор, пока не выполнится условие |Xn-1-Xn| < e.

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

Описание алгоритма решения системы линейных уравнений методом Гаусса-Зейделя:

Задаем точность вычислений tochn и максимальное количество итераций метода Гаусса-Зейделя max_k.

Задаем коэффициенты исходной системы линейных уравнений a(n,n) и правые части b(n).

Задаем начальные значения решений системы x0(n).

В соответствии с методом Гаусса-Зейделя вычисляем вспомогательную матрицу c(n,n)=a(n,n)-e(n,n), где e(n,n)=0 при i<>j, и e(n,n)=1 при i=j.

Задаем равными нулю количество итераций метода – k и количество «правильно» найденных значений x(n) – corr.

Задаем условный цикл по k, с условием повторения тела цикла пока количество «правильно» найденных значений x(n) – corr меньше количества уравнений n.

Зануляем значений «правильно» найденных значений corr=0 на данной итерации и увеличиваем счетчик цикла k=k+1.

В соответствии с методом Гаусса-Зейделя, используя найденные ранее значения вспомогательной матрицы c(n,n), вычисляем произведение матрицы c(n,n) и xk-1(n).

Вычисляем xk(1…n)=b(1…n)- c(n,n)xk-1(n).

Подсчитываем количество «правильно» (т.е. с заданной точностью) вычисленных значений xk(1…n).

Копируем вычисленные значения xk(1…n) в x0(1…n) для следующей итерации метода.

Выводим на экран значения номера итерации, количество «правильно» вычисленных xk(1…n), а также сами значения xk(1…n).

Задаем ветвление: если значение счетчика итераций k равно максимально допущенному количеству max_k задаем значение «правильно» вычисленных xk(1…n) – corr равное количеству уравнений системы n.

Конец итераций по k.

Задаем ветвление: если счетчик итераций метода k достиг максимально допустимого количества, то выводим на экран «Решение не найдено за max_k итераций», иначе – вывод на экран сообщения «Решение найдено за k итераций» и вычисленные значения решений системы линейных уравнений - xk(1…n).

Конец алгоритма.

Пример алгоритма решения системы линейных уравнений методом Гаусса-Зейделя на естественном языке:

n=размерность_системы

dec=количество_знаков_после_запятой

tochn=1/(10^dec-1)

max_k=максимальное_число_итераций

Определить Массив a(n,n),c(n,n),b(n),x0(n),x(n)

Цикл по i от 1 до n

Цикл по j от 1 до n

a(i,j)=Если(i=j,Случайный(),0.1*Случайный())

c(i,j)=0

Конец Цикла

b(i)=10*Случайный()

Конец Цикла

Вызвать Печать_Матрицы(@a,@b,n,dec)

Цикл ПО i от 1 до n

x0(i)=b(i)

Конец Цикла

Цикл по i от 1 до n

Цикл по j от 1 до n

c(i,i)=a(i,i)-Если(i=j,1,0)

Конец Цикла

Конец Цикла

k=0

corr=0

Цикл Пока corr<n

corr=0

k=k+1

Цикл по i от 1 до n

s=0

Цикл по j от 1 до n

s=s+c(i,j)*x0(j)

Конец Цикла

x(i)=b(i)-s

Конец Цикла

Цикл по i от 1 до n

Если Модуль(x(i)-x0(i))<tochn Тогда

corr=corr+1

Конец Если

x0(i)=x(i)

Конец Цикла

Печать " k= "+k

Печать " correct x "+corr

Вызвать Печать_Вектор(@x,n,dec)

corr=Если(k>max_k-1,n,corr)

Конец Цикла Пока

Если k=max_k Тогда

Печать " Решения не найдены за " + max_k+ " итераций "

Иначе

Печать " Необходимая точность достигнута за " + k+ " итераций"

Печать " Решения системы найдены "

Вызвать Печать_Вектора(@x,n,dec)

Конец Если

Определить Процедуру Печать_Вектора

Параметры x,n,dec

Определить Массив x(n)

Цикл по i от 1 до n

Печать x(i)

Конец Цикла

Конец Определения Процедуры

Определить Функцию Печать_Матрицы

Параметры a,b,n,dec

Определить Массив a(n,n),b(n)

Цикл по i от 1 до n

Цикл по j от 1 до n

Печать a(i,j)

Конец Цикла

Печать " :" + b(i)

Конец Цикла

Возврат

Конец Определения Функции

Пример реализации алгоритма решения системы линейных уравнений методом Гаусса-Зейделя на VFP:

CLEAR

n=3

dec=3

tochn=1/(10^dec-1)

max_k=500

DIMENSION a(n,n),c(n,n),b(n),x0(n),x(n)

FOR i=1 TO n

FOR j=1 TO n

a(i,j)=IIF(i=j,RAND(),0.1*RAND())

c(i,j)=0

ENDFOR

b(i)=10*RAND()

ENDFOR

Print_Matrix(@a,@b,n,dec)

FOR i=1 TO n

x0(i)=b(i)

ENDFOR

FOR i=1 TO n

FOR j=1 TO n

c(i,i)=a(i,i)-IIF(i=j,1,0)

ENDFOR

ENDFOR

k=0

corr=0

DO WHILE corr<n

corr=0

k=k+1

FOR i=1 TO n

s=0

FOR j=1 TO n

s=s+c(i,j)*x0(j)

ENDFOR

x(i)=b(i)-s

ENDFOR

FOR i=1 TO n

IF ABS(x(i)-x0(i))<tochn then

corr=corr+1

ENDIF

x0(i)=x(i)

ENDFOR

?

? " k= "+STR(k,5,0)," )"

? " correct x "+STR(corr,5,0)

Print_Vector(@x,n,dec)

corr=IIF(k>max_k-1,n,corr)

ENDDO

IF k=max_k then

?

? " Решения не найдены за " + STR(max_k,dec,0)+ " итераций "

ELSE

?

? " Необходимая точность достигнута за " + STR(k,dec,0)+ " итераций "

? " Решения системы найдены "

Print_Vector(@x,n,dec)

ENDIF

PROCEDURE Print_Vector

LPARAMETERS x,n,dec

DIMENSION x(n)

?

FOR i=1 TO n

?STR(x(i),dec*2-2,dec)

ENDFOR

ENDPROC

FUNCTION Print_Matrix

LPARAMETERS a,b,n,dec

DIMENSION a(n,n),b(n)

FOR i=1 TO n

?

FOR j=1 TO n

?? STR(a(i,j),dec*2+2,dec)

ENDFOR

?? " :" + STR(b(i),dec*2+2,dec)

ENDFOR

RETURN

ENDFUNC

В данной реализации значения коэффициентов матрицы системы уравнений a(n,n) и правых частей уравнений b(n) заданы случайным образом, а начальные значения вектора решений равны вектору правой части системы x0(n)= b(n).

Пример реализации алгоритма решения системы линейных уравнений методом Гаусса-Зейделя на VBA:

Sub Gauss_Zeidel()

Dim a(), b(), x0(), x()

n = 3

dec = 3

tochn = 1 / (10 ^ dec - 1)

max_k = 500

ReDim a(n, n): ReDim b(n): ReDim x0(n): ReDim x(n)

For i = 1 To n

For j = 1 To n

a(i, j) = IIf(i = j, Rnd(), 0.1 * Rnd())

Next j

b(i) = 10 * Rnd()

Next i

Debug.Print "КОЕФИЦИЕНТЫ СИСТЕМЫ А(N,N) И B(N)"

Call Print_Matrix(a(), b(), n, dec)

Debug.Print

For i = 1 To n

x0(i) = b(i)

Next i

For i = 1 To n

a(i, i) = a(i, i) - 1

Next i

k = 0

corr = 0

Do While corr < n

corr = 0

k = k + 1

For i = 1 To n

s = 0

For j = 1 To n

s = s + a(i, j) * x0(j)

Next j

x(i) = b(i) - s

Next i

For i = 1 To n

If Abs(x(i) - x0(i)) < tochn Then

corr = corr + 1

End If

x0(i) = x(i)

Next i

Debug.Print " Итерация k = " & k & " Найдено " & corr & " из " & n & " решений "

'Call Print_Vector(x(), n, dec)

corr = IIf(k > max_k - 1, n, corr)

Loop

If k = max_k Then

Debug.Print

Debug.Print " Решения не найдены " & max_k & " итераций "

Else

Debug.Print

Debug.Print " Необходимая точность достигнута за " & k & " итераций "

Debug.Print " Решения системы найдены "

Call Print_Vector(x(), n, dec)

End If

End Sub

Sub Print_Vector(x(), n, dec)

Dim i

Dim DStr, str

DStr = "0."

For i = 1 To dec

DStr = DStr + "0"

Next i

str = ""

For i = 1 To n

str = str & "X(" & i & ") = " & Format(x(i), DStr) & vbCrLf

Next i

Debug.Print str

End Sub

Sub Print_Matrix(a(), b(), n, dec)

Dim i

Dim DStr, str

DStr = "0."

For i = 1 To dec

DStr = DStr + "0"

Next i

str = ""

For i = 1 To n

str = str & vbCrLf

For j = 1 To n

str = str & Format(a(i, j), DStr) & " : "

Next j

str = str & " : " & Format(b(i), DStr)

Next i

Debug.Print str

End Sub

Результат работы программы на VBA:

КОЕФИЦИЕНТЫ СИСТЕМЫ А(N,N) И B(N)

0,799 : 0,096 : 0,094 : : 1,143

0,063 : 0,599 : 0,025 : : 8,602

0,044 : 0,025 : 0,379 : : 5,266

Итерация k = 1 Найдено 0 из 3 решений

Итерация k = 2 Найдено 0 из 3 решений

Итерация k = 3 Найдено 0 из 3 решений

Итерация k = 4 Найдено 0 из 3 решений

Итерация k = 5 Найдено 0 из 3 решений

Итерация k = 6 Найдено 0 из 3 решений

Итерация k = 7 Найдено 0 из 3 решений

Итерация k = 8 Найдено 0 из 3 решений

Итерация k = 9 Найдено 1 из 3 решений

Итерация k = 10 Найдено 1 из 3 решений

Итерация k = 11 Найдено 1 из 3 решений

Итерация k = 12 Найдено 1 из 3 решений

Итерация k = 13 Найдено 1 из 3 решений

Итерация k = 14 Найдено 1 из 3 решений

Итерация k = 15 Найдено 2 из 3 решений

Итерация k = 16 Найдено 2 из 3 решений

Итерация k = 17 Найдено 2 из 3 решений

Итерация k = 18 Найдено 2 из 3 решений

Итерация k = 19 Найдено 3 из 3 решений

Необходимая точность достигнута за 19 итераций

Решения системы найдены

X(1) = -1,800

X(2) = 14,013

X(3) = 13,206

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]