Разработка программы для решения систем линейных алгебраических уравнений методом Зейделя
Системы линейных уравнений широко используются в области физики и смежных с ней наук: теории относительности, атомной физике, при составлении прогнозов погоды и т. д. ПОЯСНИТЕЛЬНАЯ ЗАПИСКА Тема работы: Разработка программы для решения систем линейных алгебраических уравнений методом Зейделя Автор: студент гр Морозов А. В. Методические указания к курсовой работе Информатика решение систем линейных… Читать ещё >
Разработка программы для решения систем линейных алгебраических уравнений методом Зейделя (реферат, курсовая, диплом, контрольная)
Министерство образования Российской Федерации Национальный минерально-сырьевой университет «Горный»
Кафедра информатики и компьютерных технологий КУРСОВАЯ РАБОТА
по дисциплине Информатика
ПОЯСНИТЕЛЬНАЯ ЗАПИСКА Тема работы: Разработка программы для решения систем линейных алгебраических уравнений методом Зейделя Автор: студент гр Морозов А.В.
Проверил: ассистент /Кротова С.Ю./
Санкт-Петербург 2012
Аннотация
Пояснительная записка представляет собой отчет о выполнении курсовой работы на тему «Разработка программы для решения систем линейных алгебраических уравнений методом Зейделя». В ней рассмотрены вопросы об оформлении решения систем уравнений на языке Visual Basic for Application.
Страниц ___.
- Введение
- Теория метода
- Вычислительная схема метода Зейделя
- Разработка программы на языке VBA
- Решение СЛАУ методом Зейделя в MS Excel
- Решение СЛАУ методом Зейделя в MathCad
- Решение СЛАУ методом Зейделя в MatLab
- Заключение
- Библиографический список
Система m линейных уравнений с n неизвестными имеет сл. вид:
где
корни СЛАУ;
коэффициенты системы;
свободные члены.
Если число m уравнений равно числу n неизвестных, то такая система называется квадратной. В данной работе рассматривается решение квадратных систем.
В матричном виде квадратная СЛАУ выглядит следующим образом:
или, где
А — матрица коэффициентов системы;
х — столбец неизвестных;
b — столбец свободных членов.
Для матрицы А существует невырожденная матрица С, если. Тогда. Если матрица С является обратной для А, т. е., тогда:
Для решения СЛАУ разработано множество методов. Прямые методы позволяют найти решение за определенное количество шагов. К ним относятся:
1) Метод Гаусса;
2) Метод Гаусса — Жордана;
3) Метод Крамера;
4) Матричный метод и др.
Итерационные методы позволяют найти решение СЛАУ путем уточнений начальных приближений многократным повторением одинаковых итераций. Число итераций зависит от заданной точности решения.
Наиболее распространенные итерационные методы:
1) Метод Якоби (метод простой итерации);
2) Метод Гаусса — Зейделя.
К решению систем линейных уравнений сводятся такие группы задач:
1) задачи механики (статические, теплотехнические);
2) задачи из геодезии, связанные с построением карт на основании данных геодезической съемки;
3) задачи приближенного решения уравнений, имеющих большое распространение в высшей математике;
4) системы линейных уравнений широко используются в области физики и смежных с ней наук: теории относительности, атомной физике, при составлении прогнозов погоды и т. д.
Перечисленные задачи не исчерпывают всех случаев использования систем линейных уравнений, но обнаруживают, насколько часто приходится сталкиваться при решении задач математики и естествознания с необходимостью исследовать и точно или приближенно решить систему линейных уравнений.
линейное алгебраическое уравнение программа
Теория метода
Метод Гаусса-Зейделя можно рассматривать как модификацию метода Якоби. Основная идея модификации состоит в том, что новые значения используются здесь сразу же по мере получения, в то время как в методе Якоби они не используются до следующей итерации.
Пусть дана квадратная система линейных алгебраических уравнений с n неизвестными, корни которой необходимо найти с заданной точностью :
или
Для решения данной СЛАУ можно применить метод Зейделя, если выполняется условие сходимости для матрицы А. Оно заключается в следующем: модули диагональных элементов строки или столбца матрицы должны быть больше суммы модулей недиагональных элементов этой строки или столбца, т. е.:
Преобразуем матричное выражение к виду, разрешив n-ю строку относительно переменной :
Придадим начальные приближения, значения которых можно рассчитать как:. Посчитаем первые приближения, подставив в систему. Соответственно, на k-м шаге приближения будут рассчитываться как:
В общем виде расчетные формулы выглядят:
Из вычислительной математики известие факт, что для СЛАУ в виде, при условии сходимости матрицы, в процессе итераций получаемые приближения сходятся к корням уравнения при любом начальном приближении, т. е., где i-й корень СЛАУ. Количество итераций зависит от необходимой точности. Если задана точность, то процесс уточнения неизвестных прекращают, когда выполняется условие критерия близости на k-м шаге:
Вычислительная схема метода Зейделя
Рассмотрим вычислительную схему метода Зейделя на примере системы уравнений задания:
Матрица системы
вектор-столбец
1. Задается точность ()
2. Проверяется условие сходимости матрицы:
верно;
верно;
верно.
3. Вычисление начальных приближений:
4. Нахождение приближений:
5. Критерий близости:
заданная точность не достигнута.
Дальнейшие итерации выполняются аналогично (таблица 1).
Таблица 1
Результат вычислений методом Зейделя
k | ||||||||
0,187 | — 0,169 | — 0,137 | ||||||
0,187 | — 0,173 | — 0,076 | 0,0007 | 0,0044 | 0,0615 | 0,0615 | ||
0, 190 | — 0,155 | — 0,085 | 0,0024 | 0,0179 | 0,0088 | 0,0179 | ||
0,189 | — 0,158 | — 0,083 | 0,0010 | 0,0027 | 0,0014 | 0,0027 | ||
0,189 | — 0,158 | — 0,083 | 0,0001 | 0,0004 | 0,0002 | 0,0004 | ||
Решение достигается за 4 итерации. Корни СЛАУ:
Разработка программы на языке VBA
1. Блок-схема программы
2. Описание подпрограмм
1) Имя: VVOD
Назначение: подпрограмма, осуществляющая считывание данных с листа MS Excel.
Вход:
list — лист MS Excel, в котором содержаться исходные данные;
row — номер строки, с которой начинается считывание матрицы;
col — номер столбца, с которого начинается считывание матрицы;
n — число строк матрицы;
m — число столбцов матрицы.
Выход:
М1 () — матрица исходных данных.
2) Имя: PROVERKA
Назначение: осуществляет проверку сходимости матрицы коэффициентов, сообщает результат проверки.
Вход:
list — лист MS Excel, на который выводится результат проверки сходимости;
n — число строк и столбцов матрицы;
М1 () — матрица исходных данных.
Выход: —
3) Имя: ZEIDEL
Назначение: осуществляет решение СЛАУ, выводит процесс вычислений на лист MS Excel.
Вход:
list — лист MS Excel, на который выводится вычисления;
n — число строк и столбцов матрицы;
М1 () — матрица коэффициентов;
М2 () — матрица-столбец.
Выход:
М3 () — матрица, содержащая корни СЛАУ
4) Имя: VIVOD
Назначение: подпрограмма, осуществляющая вывод корней СЛАУ на лист MS Excel
Вход:
list — лист MS Excel, в который выводятся данные;
n — число строк матрицы корней;
М3 () — матрица корней.
Выход: —
3. Листинг подпрограммы
1) Основная программа
Sub RESHENIE ()
Dim C As Integer
C = InputBox («Введите число переменных»)
ReDim A (C, C) As Single
ReDim b (C, 1) As Single
ReDim X © As Single
Call VVOD (1, 2, 1, C, C, A ())
Call VVOD (1, 2, C + 1, C, 1, b ())
Call PROVERKA (1, C, A ())
Call ZEIDEL (1, C, A (), b (), X ())
Call VIVOD (1, C, X ())
End Sub
2) Подпрограмма ввода данных
Sub VVOD (list As Integer, row As Integer, col As Integer, n As Integer, m As Integer, M1 () As Single)
Dim i As Integer
Dim j As Integer
For i = 1 To n
For j = 1 To m
M1 (i, j) = Worksheets (list). Cells (row + i — 1, col + j — 1). Value
Next j
Next i
End Sub
3) Подпрограмма проверки сходимости
Sub PROVERKA (list As Integer, n As Integer, M1 () As Single)
Dim i As Integer
Dim j As Integer
Dim d As Integer
Dim sum As Integer
Worksheets (list). Cells (1, n + 3). Value = «Проверка сходимости»
d = 0
For i = 1 To n
sum = 0
For j = 1 To n
If j <> i Then sum = sum + Abs (M1 (i, j))
Next j
If Abs (M1 (i, i)) > Abs (sum) Then d = d + 1
Next i
If d = n Then
Worksheets (list). Cells (2, n + 3). Value = «Сходится»
Else
Worksheets (list). Cells (2, n + 3). Value = «Не сходится»
End If
End Sub
4) Подпрограмма решения СЛАУ методом Зейделя
Sub ZEIDEL (list As Integer, n As Integer, M1 () As Single, M2 () As Single, M3 () As Single)
Dim i As Integer
Dim j As Integer
Dim g As Integer
Dim S As Single
ReDim m (n) As Single
ReDim X (n) As Single
Dim e As Single
Dim f As Single
Dim v As Single
e = 0.001
g = o
'Подсчет начальных приближений. Подготовка таблицы решения
For i = 1 To n
X (i) = M2 (i, 1) / M1 (i, i)
Worksheets (list). Cells (n + 3, 1). Value = «№»
Worksheets (list). Cells (n + 3,2). Value = Str (g)
Worksheets (list). Cells (n + 4 + i, 1). Value = «X» + Str (i)
Worksheets (list). Cells (2 * n + 5 + i, 1). Value = «раз-ть X» + Str (i)
Worksheets (list). Cells (3 * n + 7, 1). Value = «MAX разность»
Worksheets (list). Cells (n + 4 + i, g + 2). Value = CInt (X (i) * 1000) / 1000
Next i
Do
'Подсчет суммы элементов
For i = 1 To n
For j = 1 To n
If i <> j Then S = S + M1 (i, j) * X (j)
Next j
'Нахождение приближений
v = X (i)
X (i) = (1/M1 (i, i)) * (M2 (i, 1) — S)
Worksheets (list). Cells (n + 4 + i, g + 3). Value = CInt (X (i) * 1000) / 1000
S = 0
m (i) = Abs (X (i) — v)
Worksheets (list). Cells (2 * n + 5 + i, g + 3). Value = CInt (m (i) * 10 000) / 10 000
'Выбор наибольшей разности
f = m (1)
j = 1
Do
If f < m (j) Then f = m (j)
j = j + 1
Loop Until j > n
Worksheets (list). Cells (3 * n + 7, g + 3). Value = CInt (f * 10 000) / 10 000
Next i
g = g + 1
Worksheets (list). Cells (n + 3, g + 2). Value = g
Loop Until f < e
For i = 1 To n
M3 (i) = X (i)
Next i
End Sub
5) Подпрограмма вывода корней СЛАУ
Sub VIVOD (list As Integer, n As Integer, M3 () As Single)
Dim i As Integer
Dim col As Integer
col = n + 6
Worksheets (list). Cells (1, col). Value = «Корни СЛАУ»
For i = 1 To n
Worksheets (list). Cells (1 + i, col). Value = «X» + Str (i)
Worksheets (list). Cells (1 + i, col + 1). Value = CInt (M3 (i) * 1000) / 1000
Next i
End Sub
Результат работы программы
Сначала пользователю необходимо ввести СЛАУ в матричном в виде: выписать матрицу коэффициентов при неизвестных и матрицу свободных членов (рис.1).
Рис. 1.
При запуске программы появляется диалоговое окно, в котором предлагается ввести число переменных СЛАУ (рис.2).
Рис. 2.
Пользователю необходимо ввести число переменных (равно числу строк СЛАУ), после чего программа выдает на лист MS Excel корни уравнения, а также вычисления, выполняемые в каждой итерации (рис.3).
Самостоятельный ввод пользователем числа переменных делает программу для решения СЛАУ методом Зейделя применимой для любого числа переменных.
Рис. 3.
Решение СЛАУ методом Зейделя в MS Excel
Рис. 4.
Решение СЛАУ методом Зейделя в MathCad
Проверка сходимости
Начальные приращения
Первая итерация
Вторая итерация
Третья итерация
Четвертая итерация
Решение СЛАУ методом Зейделя в MatLab
clc; clear all, close all;
%Исходные данные
A= [7.77, 0.27, — 0.29;
1.15 — 6.22, 1.77;
1.05, 4.52, 9.544;];
b= [1.45, 1.05, — 1.31];
X= [0 0 0;
0 0 0];
e=0.001;
%Начальные приближения
x1=b (1,1) /A (1,1);
x2=b (1,2) /A (2,2);
x3=b (1,3) /A (3,3);
m=max (abs (x1), abs (x2));
m=max (m, abs (x3));
if m
disp ([x1 x2 x3])end;
%Итерации
while m>e
X (1,1) =x1;
X (1,2) =x2;
X (1,3) =x3;
x1= ((b (1,1) — A (1,2) *x2-A (1,3) *x3) /A (1,1));
x2= ((b (1,2) — A (2,1) *x1-A (2,3) *x3) /A (2,2));
x3= ((b (1,3) — A (3,1) *x1-A (3,2) *x2) /A (3,3));
X (2,1) = (x1-X (1,1));
X (2,2) = (x2-X (1,2));
X (2,3) = (x3-X (1,3));
m=max (abs (X (2,1)), abs (X (2,2)));
m=max (m, abs (X (2,3)));
end;
disp ([x1 x2 x3])
Рис. 5.
Заключение
В ходе выполнения работы нами была разработана программа на языке VBA, позволяющая находить корни СЛАУ методом Зейделя. Правильность работы программы была проверена аналогичным методом в редакторе MS Excel и математических пакетах MathCad и MatLab. В результате проверки корни СЛАУ, вычисленные программой, и корни, найденные с помощью вышеуказанных средств, совпали. Разработанная программа применима для решения СЛАУ методом Зейделя с другим числом переменных при условии сходимости матрицы коэффициентов.
Библиографический список
1. Методические указания к курсовой работе Информатика решение систем линейных алгебраических уравнений итерационными методами. Санкт-Петербург, 2004 г.
2. Демидович Б. П., Марон И. А. Основы вычислительной математики. Учебн. пособие для ВТУЗов. Изд.4-е, испр. М.: Наука, 1970.
3. Зельднер Г. А. Программируем на языке QuickBASIC 4.5 Изд 2-е, исправленное и дополненное, М.: ABF, 1996.
4. Хэлворсон М. Эффективная работа с Microsoft Office 2000. СПб, М, Харьков, Минск: Питер, 2001.