Файл: Метод Гаусса-Зейделя.doc

Скачать файл (0,07Мб)

Заказать решение

ВУЗ: Алтайский Государственный Университет

Категория: Учебное пособие

Дисциплина: Программирование

Добавлен: 29.10.2018

Просмотров: 376

Скачиваний: 10

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.

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

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

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

A*X=B, (7.6)

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

X=B-C*X, (7.7)

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

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

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

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

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

Задаем точность вычислений tochn и максимальное количество итераций метода Гаусса-Зейделя max_k.
Задаем коэффициенты исходной системы линейных уравнений a(n,n) и правые части b(n).
Задаем начальные значения решений системы x₀(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) и x_k_-1(n).
Вычисляем x_k(1…n)=b(1…n)- c(n,n)* x_k_-1(n).
Подсчитываем количество «правильно» (т.е. с заданной точностью) вычисленных значений x_k(1…n).
Копируем вычисленные значения x_k(1…n) в x₀(1…n) для следующей итерации метода.
Выводим на экран значения номера итерации, количество «правильно» вычисленных x_k(1…n) а также сами значения x_k(1…n).
Задаем ветвление: если значение счетчика итераций k равно максимально допущенному количеству max_k задаем значение «правильно» вычисленных x_k(1…n) – corr равное количеству уравнений системы n.
Конец итераций по k.
Задаем ветвление: если счетчик итераций метода k достиг максимально допустимого количества, то выводим на экран «Решение НЕ найдено за max_k итераций», иначе – вывод на экран сообщения «Решения найдено за k итераций» и, собственно, вычисленные значения решений системы линейных уравнений - x_k(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

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) заданы случайным образом, а начальные значения вектора решений равны вектору правой части системы x₀(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

Смотрите также файлы

Графика и рекурсивные алгоритмы.doc

Вычисление определенных интегралов.doc

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

Cлучайные величины.doc

А.Т. Зуб Управление проектами.pdf

Файл: Метод Гаусса-Зейделя.doc

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

Смотрите также файлы

Информация

Списки файлов

Дополнительно