Решение систем линейных уравнений
.pdf
Рис. 2.5 – Блок «Проверка неравенства нулю диагональных элементов» и блок «Проверка условия сходимости»
Рис. 2.6 – Блок «Подсчет коэффициентов βi и αij »
51
Рис. 2.7. Блок «Нахождение решения системы»
52
2.4.МЕТОД ПРОГОНКИ
Метод прогонки применяется для решения систем линейных уравнений с трехдиагональными матрицами вида:
a11x1 + a12 x2 |
|
|
|
|
|
|
|
|
|
|
|
= b1 |
|||||||
a |
21 |
x + a |
22 |
x |
2 |
+ a |
23 |
x |
|
|
|
|
|
|
|
|
|
= |
b |
|
1 |
|
|
3 |
|
|
|
|
|
|
|
|
|
|
2 |
||||
|
|
a32 x2 |
+ a33x3 + a34x4 |
|
|
|
|
|
|
|
|
|
|
b3 (2.13) |
|||||
|
|
|
|
|
|
|
|
|
|
|
= |
||||||||
|
|
|
|
|
|
|
|
|
K |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
a |
nn−1 |
x |
n−1 |
+ |
a |
nn |
x |
n |
= |
b |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
n |
||||
Матрица A этой системы имеет вид:
|
|
|
|
|
|
|
|
|
|
a |
|
|
a |
0 |
|
|
0 |
|
|
|
0 |
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
11 |
|
|
12 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
a21 |
|
|
a22 |
a23 |
|
|
0 |
|
|
|
0 |
|
|
|
|
|
||||||
|
|
|
|
|
|
A = |
0 |
|
|
a |
|
|
a |
|
|
|
a |
|
|
|
|
|
0 |
|
|
|
|
(2.14) |
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
32 |
|
33 |
|
|
|
34 |
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
K |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
|
|
0 |
|
0 ann−1 |
|
|
|
|
|
|
|
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
ann |
|
|
|
|
||||||||||||||
Из первого уравнения системы (2.13) вычислим |
x1: |
|
|
|
|
|||||||||||||||||||||||||||
|
|
|
x |
|
= α |
1 |
x |
2 |
+ β |
1 |
, где |
α |
1 |
= − |
a12 |
, |
|
β = |
b1 |
. |
|
|||||||||||
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||||
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
a11 |
|
|
1 |
|
a11 |
|
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
Подставим полученное выражение для x1 во второе уравнение |
||||||||||||||||||||||||||||||||
системы (2.13), найдем x2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||
x |
|
= α |
|
x |
|
+ β |
|
|
, |
α |
2 |
= − |
|
|
a23 |
|
|
, |
|
β |
2 |
= |
b2 − a21β 1 |
. |
||||||||
2 |
2 |
3 |
2 |
|
|
|
|
|
|
|
|
|
||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
a22 + a21α 1 |
|
|
a22 + a21α 1 |
|
||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||
53
Выполняя последовательно эти действия, на i-ом шаге получим:
x i = α i xi+1 + β i , α i = − |
a i,i+1 |
, |
β i = |
bi − ai, i−1β i−1 |
(2.15) |
|
a i,i + a i,i−1α i−1 |
a i,i + a i,i−1α i−1 |
|||||
|
|
|
|
Если в последнее уравнение системы (2.13) подставить xn-1, вычисленное по формулам (2.15), то можно получить уравнение для вычисления xn.
a |
|
(α |
|
x |
|
+ β |
|
) + a |
|
x |
|
= b |
, |
x |
|
= |
bn − an,n−1 |
β n−1 |
. |
|
n,n−1 |
n−1 |
n |
n−1 |
n,n |
n |
n |
|
|
|
|||||||||||
|
|
|
||||||||||||||||||
|
|
|
|
|
|
|
n |
|
|
an,n−1α n−1 |
+ an,n |
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
Значения остальных неизвестных легко находятся по формулам (2.15). Метод прогонки является двухпроходным. На прямом проходе вычисляются коэффициенты αi и βi , а на обратном неизвестные xi.
На рис. 2.8 представлена блок-схема алгоритма метода прогон-
ки.
54
Рис. 2.8. Блок-схема метода прогонки
55
2.5.РЕКОМЕНДАЦИИ ПО ВЫБОРУ МЕТОДА РЕШЕНИЯ СИСТЕМЫ ЛИНЕЙНЫХ УРАВНЕНИЙ
Для практических вычислений и прямые и итерационные методы имеют свои преимущества и недостатки.
Прямые методы решения систем линейных уравнений могут, в принципе (с точностью ошибок округления), дать точное решение, если оно существует. Но из этого вовсе не следует, что решение, полученное с помощью прямого метода, обязательно будет точнее, чем при использовании итерационного метода, так как ошибки округления могут накапливаться и привести к бессмысленным результатам.
Итерационные методы могут оказаться наиболее удачными, так как при их использовании ошибки округления не накапливаются. Такие ошибки эквивалентны некоторому ухудшению очередного приближения, и итерационная последовательность по-прежнему будет сходиться к решению, а внесенная ошибка будет затухать. Говорят, что итерационные методы обладают свойством самоисправляемости.
56
КОНТРОЛЬНЫЕ ВОПРОСЫ
1.Приведите примеры точных и итерационных методов решения систем линейных уравнений.
2.В чем состоит идея метода Гаусса?
3.В каких случаях систему линейных уравнений нельзя решить методом Гаусса?
4.В чем состоит идея метода Халецкого?
5.Опишите суть метода итераций для решения систем линейных уравнений.
6.Сформулируйте условие сходимости метода итераций для решения систем линейных уравнений.
7.В чем состоит идея метода прогонки, когда он применяется?
57
СПИСОК ЛИТЕРАТУРЫ
1.Вычислительная математика в примерах и задачах. Н.В. Копченова, И.А. Марон. М.: Наука, 1972. 366 с.
2.Алексеев Е.Р., Чеснокова О.В. Решение задач вычислительной ма-
тематики в пакетах MathCad 12, MatLab 7, Maple 9. М.: НТ Пресс, 2006. 496 с.
3.Кабальнов Ю. С., Карчевская М. П., Рамбургер О.Л. Применение Excel в базовом курсе информатики: учебное пособие. Уфа:
УГАТУ, 2006. 177 с.
4.Мак-Кракен Д., Дорн У. Численные методы и программирование.
М.: Мир, 1977. 583 с.
58
ПРИЛОЖЕНИЕ А
ЛИСТЫ ЗАДАНИЙ
59
Федеральное агентство по образованию Государственное образовательное учреждение высшего профессионального образования
«Уфимский государственный авиационный технический университет» Кафедра информатики
Расширенное описание задания на курсовую работу по дисциплине «Информатика»
Тема 6, Вариант 1
Студент
Факультет, группа ________________
Консультант
Тема: Программирование и исследование алгоритмов решения систем линейных уравнений.
Основное содержание: Расчет токов разветвленной цепи при помощи законов Кирхгофа и метода прогонки.
Описание: На рисунке приведена электрическая схема. Известны значения сопротивлений нагрузок (Ri), ЭДС источников (Ei) и их внутренних сопротивлений (ri). Найти все токи, протекающие через нагрузки в цепи.
При помощи законов Кирхгофа составить систему уравнений и привести ее к трехдиагональному виду. Создать приложение для решения данной системы методом прогонки.
Ввод данных осуществляется пользователем с клавиатуры.
Результаты расчета выводятся на экран и сохраняются в файле.
Приложение должно содержать не менее трех окон, а также текстовое меню в главном окне, позволяющее выполнять основные действия.
В одном из окон приложения должна отображаться исходная электрическая схема.
Дополнительные требования к оформлению
На каждой форме внизу и в верхнем колонтитуле пояснительной записки должны быть приведены сведения о задании: Факультет, группа, Фамилия,
имя, отчество (полностью), Тема, вариант.
Консультации:
День недели_____________________, Время: _______________
60