- •Основы алгоритмизации и языки программирования Учебно-методическое пособие
- •Содержание
- •Лабораторная работа №1. Базовые языковые конструкции vfp и vba. Основы работы с данными
- •Контрольные вопросы
- •Задания
- •Лабораторная работа №2. Определение корней уравнений Определение корня уравнения методом деления отрезка пополам (дихотомии)
- •Определение корня одномерного уравнения методами касательных и секущих
- •Определение корня одномерного уравнения методом простой итерации
- •Задания
- •Контрольные вопросы
- •Определение максимального и минимального значения функции двух переменных методом градиентного спуска (подъема)
- •Контрольные вопросы
- •Задания
- •Лабораторная работа №4. Рекурсия. Рекурсивные алгоритмы Рекурсия. Рекурсивные алгоритмы
- •Графика и рекурсивные алгоритмы
- •Контрольные вопросы
- •Задания
- •Лабораторная работа №5. Аппроксимация, интерполяция и экстраполяция Простейшие способы интерполяции и экстраполяции данных
- •Аппроксимация выборки случайных чисел методом наименьших квадратов
- •Контрольные вопросы
- •Задания
- •Лабораторная работа №6. Решение систем линейных уравнений Решение систем линейных уравнений методом Гаусса
- •Решение систем линейных уравнений методом Гаусса с выбором максимального элемента
- •Контрольные вопросы
- •Задания
- •Лабораторная работа №7. Итерационные методы решения систем линейных уравнений. Приложения численных методов решения систем линейных уравнений Метод Зейделя
- •Метод Гаусса-Зейделя
- •Обращение матрицы nхn с использованием метода Гаусса
- •Контрольные вопросы
- •Задания
- •Лабораторная работа №8. Вычисление определенных интегралов Вычисление определенных интегралов методом прямоугольников
- •Вычисление определенных интегралов методом трапеций
- •Вычисление интеграла по методу Симпсона
- •Контрольные вопросы
- •Задания
- •Лабораторная работа №9. Численное решение дифференциальных уравнений Методы численного решения дифференциальных уравнений первого порядка
- •Метод Эйлера
- •Метод Кранка-Николсона
- •Метод Рунге-Кутты четвертого порядка для решения уравнения первого порядка
- •Методы численного решения систем дифференциальных уравнений Гармонические колебания
- •Затухающие колебания
- •Периодический процесс с затуханием и с внешней силой
- •Решение системы дифференциальных уравнений методом Эйлера
- •Решение системы дифференциальных уравнений первого порядка методом Рунге-Кутты
- •Контрольные вопросы
- •Задания
- •Лабораторная работа №10. Генерация равномерных и неравномерных распределений случайных чисел Использование гистограмм для отображения характера распределения случайной величины
- •Генератор дискретно-распределенных значений
- •Генерация дискретных распределений с заданным характером распределения вероятностей
- •Генерация непрерывных распределений вещественных величин Псевдонормальное распределение
- •Генерация линейно возрастающего распределения
- •Контрольные вопросы
- •Задания
- •Список рекомендуемой литературы и источников
Метод Гаусса-Зейделя
Для решения систем линейных уравнений наряду с прямыми методами решений (метод Гаусса) используются и итерационные методы. Одним из наиболее простых итерационных методов решения систем линейных уравнений является с метод Гаусса-Зейделя.
В соответствии с методом Гаусса-Зейделя исходную систему линейных уравнений
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
