- •Часть I
- •Введение
- •1. Метод Гаусса
- •1.1. Описание метода Гаусса
- •1.2. Норма матриц и обусловленность
- •1.4. Задание
- •1.5. Порядок выполнения работы на компьютере
- •Порядок выполнения работы
- •1.5. Содержание отчета
- •2. Метод lu-разложения и метод Холесского для решения слау
- •2.1. Алгоритм lu-разложения
- •2.2. Алгоритм треугольного разложения положительно определенных симметричных матриц и его применение для решения слау
- •2.4. Задание
- •2.5. Порядок выполнения работы на компьютере
- •Порядок выполнения работы
- •2.5.2. Разложение Холесского
- •2.6. Содержание отчета
- •3. Метод прогонки
- •3.1. Описание метода прогонки
- •3.3. Задание
- •3.4. Порядок выполнения работы на компьютере
- •Порядок выполнения работы
- •3.5. Содержание отчета
- •Библиографический список
3. Метод прогонки
3.1. Описание метода прогонки
Метод прогонки представляет собой вариант метода Гаусса, примененный к специальным системам линейных алгебраических уравнений (СЛАУ), и учитывающий ленточную структуру матрицы системы.
Матрица A такая, что ее элементы для всех , называется ленточной.
Пусть имеем, СЛАУ со специальной трехдиагональной формой матрицы, т. е. с матрицей, все элементы которой, не лежащие на главной и двух побочных диагоналях, равны 0 ( при и )
;
, ; (3.1)
,
или в матричной форме: , где вектор неизвестных; - вектор правых частей; A квадратная матрица
. (3.2)
Системы вида (3.1) возникают при аппроксимации краевых задач математической физики, описываемых обыкновенными дифференциальными уравнениями второго порядка с постоянными и переменными коэффициентами, а также уравнениями в частных производных. Ставится задача разработать экономичные методы решения задач вида (3.1), число арифметических операций для которых пропорционально числу неизвестных. Таким методом для системы (3.1) является метод прогонки.
Специфика матрицы A системы (3.1) состоит в расположении ненулевых элементов, матрица A разреженная матрица, из элементов которой ненулевыми являются не более элементов. Это позволяет получить для решения СЛАУ простые расчетные формулы. Будем искать решение (3.1) в виде
, (3.3)
с неопределенными коэффициентами , . Выражение подставим в (3.1)
с учетом (3.3) имеем
.
Это равенство имеет место для любых , если
, .
Отсюда получаем рекуррентные формулы для определения ,
, ; (3.4)
. (3.5)
Коэффициенты , , называются прогоночными.
Если коэффициенты и известны, а также известно то, двигаясь справа налево (от i+1 к i) последовательно, определяем все . Задача нахождения , по формулам (3.4), (3.5) решается слева направо (от i к i+1). Начальные значения прогоночных коэффициентов , можно определить следующим образом. Полагаем в формуле (3.3) , имеем , а из первого уравнения (3.1) , откуда
. (3.6)
Значение определяется следующим образом. Полагаем в формуле (3.3) , имеем , а из последнего уравнения (3.1) , откуда
. (3.7)
Расчетные формулы (3.3) - (3.7) можно получить также из (3.1), если применить метод исключения Гаусса. Прямой ход метода заключается в том, что на первом шаге из всех уравнений системы (3.1) при помощи первого уравнения исключается , затем из преобразованных уравнений для при помощи уравнения, соответствующего , исключается и т.д. В результате получим одно уравнение относительно . На этом прямой ход метода прогонки заканчивается. На обратном ходе для находятся .
Порядок счета в методе прогонки следующий:
- исходя из значений , , вычисленных по формулам (3.6), все остальные коэффициенты , для определяются последовательно по формулам (3.4) и (3.5);
- исходя из значения , рассчитанного по формуле (3.7), все остальные неизвестные , определяются последовательно по формуле (3.3).
Изложенный метод поэтому называется правой прогонкой.
Аналогично выводятся формулы левой прогонки:
, , ; (3.8)
, , ; (3.9)
, , . (3.10)
Здесь находятся последовательно для значений ; ход вычислений слева направо.
В случае, если необходимо найти только одно неизвестное, например, или группу идущих подряд неизвестных, целесообразно комбинировать правую и левую прогонки. При этом получается метод встречных прогонок.
Получим расчетные формулы метода встречных прогонок. Пусть , по формулам (3.4), (3.5), (3.8), (3.9) найдем прогоночные коэффициенты ; , а также ; . По формулам (3.3) и (3.10) при найдем
откуда определяем
С помощью по формулам (3.3) последовательно находятся с помощью формулы (3.10) последовательно находятся
Формулы метода встречных прогонок имеют вид
для прогоночных коэффициентов и
для определения решения.
Произведем подсчет числа арифметических действий для метода правой прогонки. Анализ формул (3.3)-(3.7) показывает, что общее число арифметических операций есть . Коэффициенты не зависят от правой части СЛАУ (3.1) и определяются только элементами , , матрицы A. Поэтому, если требуется решить серию задач (3.1) с различными правыми частями, то прогоночные коэффициенты вычисляются только для первой серии. Для каждой последующей серии задач определяются только коэффициенты и решение , причем используются ранее найденные .
На решение первой из серии задач расходуется операций, а на решение каждой следующей задачи операций. Число арифметических операций, необходимое для решения СЛАУ (3.1) методом левой прогонки и методом встречных прогонок такое же, т.е. .
Метод правой прогонки будем называть корректным, если при .
Решение находится по рекуррентной формуле (3.3). Эта формула может порождать накопление ошибок округления результатов арифметических операций. Пусть прогоночные коэффициенты и найдены точно, а при вычислении допущена ошибка , т.е. . При вычислениях с помощью формулы (3.3) мы получаем
. (3.11)
Вычитая из (3.11) значение по формуле (3.3) имеем для погрешности с заданным . Отсюда ясно, что если по модулю больше единицы, и если N достаточно велико, то вычисленное значение будет значительно отличаться от искомого решения . В этом случае говорят, что алгоритм прогонки неустойчив.
Определение. Алгоритм прогонки называется устойчивым, если , .
Условия корректности и устойчивости алгоритма правой прогонки определяются следующей теоремой.
Теорема. Пусть коэффициенты системы (3.1) действительны и удовлетворяют условиям:
, ;
, ; (3.12)
, ; (3.13)
причем хотя бы в одном из неравенств (3.12) и (3.13) выполняется строгое неравенство, т.е. матрица A имеет диагональное преобладание. Тогда для алгоритма (3.3)-(3.7) имеют место неравенства: , , , т.е. алгоритм метода правой прогонки корректен и устойчив.
Условия теоремы (3.12) и (3.13) обеспечивают также корректность и устойчивость алгоритмов левой и встречных прогонок. Эти условия сохраняются и для случая системы (3.1) с комплексными коэффициентами , , .
Легко показать, что при выполнении условий теоремы (3.12)-(3.13) система (3.1) имеет единственное решение при любой правой части. Действительно, при проверке легко убедиться в том, что матрица A представляется в виде произведения двух треугольных матриц L и R,
,
где
и . Так как
в силу выполнения условий теоремы система (3.1) имеет единственное решение при любых ее правых частях.
3.2. Варианты заданий
Вариант |
a |
b |
c |
f |
1 |
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 |
12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 |
13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25 |
37, 62, 89, 118, 149, 182, 217, 254, 293, 334, 377, 422, 469 |
2 |
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 |
12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 |
26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38 |
50, 88, 128, 170, 214, 260, 308, 358, 410, 464, 520, 578, 638 |
3 |
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 |
12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 |
13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25 |
62, 88, 116, 146, 178, 212, 248, 286, 326, 368, 412, 458, 506 |
4 |
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 |
12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 |
26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38 |
88, 127, 168, 211, 256, 303, 352, 403, 456, 511, 568, 627, 688 |
5 |
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 |
12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 |
13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25 |
87, 114, 143, 174, 207, 242, 279, 318, 359, 402, 447, 494, 543 |
6 |
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 |
12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 |
26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38 |
126, 166, 208, 252, 298, 346, 396, 448, 502, 558, 616, 676, 738 |
7 |
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 |
12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 |
13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25 |
112, 140, 170, 202, 236, 272, 310, 350, 392, 436, 482, 530, 580 |
8 |
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 |
12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 |
26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38 |
164, 205, 248, 293, 340, 389, 440, 493, 548, 605, 664, 725, 788 |
9 |
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 |
12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 |
13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25 |
137, 166, 197, 230, 265, 302, 341, 382, 425, 470, 517, 566, 617 |
10 |
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 |
12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 |
26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38 |
202, 244, 288, 334, 382, 432, 484, 538, 594, 652, 712, 774, 838 |
11 |
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 |
12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 |
13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25 |
162, 192, 224, 258, 294, 332, 372, 414, 458, 504, 552, 602, 654 |
12 |
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 |
12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 |
26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38 |
240, 283, 328, 375, 424, 475. 528, 583, 640, 699, 760, 823, 888 |
13 |
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 |
12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 |
13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25 |
187, 218, 251, 286, 323, 362, 403, 446, 491, 538, 587, 638, 691 |
14 |
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 |
12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 |
26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38 |
278, 322, 368, 416, 466, 518, 572, 628, 686, 746, 808, 872, 938 |