Численные методы линейной алгебры

3. Метод прогонки

Метод прогонки представляет собой простой и эффективный алгоритм решения систем линейных алгебраических уравнений с трехдиагональными матрицами коэффициентов следующего вида

Системы такого вида часто возникают при решении различных инженерных задач, например, при интерполяции функций сплайнами.

Преобразуем первое уравнение системы (8) к виду x 1 = 1 x 2 + 1 , где

1 = -с 1 / b 1 и 1 = -d 1 / b 1 . Подставим полученное для x 1 выражение во второе уравнение системы (8)

a 2 (1 x 2 + 1) + b 2 x 2 + c 2 x 3 = d 2 .

Представим это уравнение в виде x 2 = 2 x 3 + 2 , где 2 = -с 2 / (b 2 + a 2 1) и 2 = (d 2 - a 2 1) / (b 2 + a 2 1). Полученное для x 2 выражение подставим в третье уравнение системы (8) и т.д.

На i-м шаге (1 < i < n) процесса i-е уравнение системы принимает вид

x i = i x i+1 + i , (9)

где i = -с i / (b i + a i i-1) и i = (d i - a i i-1) / (b i + a i i-1).

На последнем n-м шаге подстановка в последнее уравнение системы (8) выражения x n -1 = n -1 x n + n -1 дает уравнение a n (n -1 x n + n -1) + b n x n = d n , из которого можно определить значение x n = n = (d n - a n n-1) / (b n + a n n-1).

Значения остальных неизвестных x i (i = n-1, n-2, ..., 1) легко вычисляются по формуле (9).

Таким образом, алгоритм прогонки, подобно методу Гаусса, включает два этапа - прямой ход (прямая прогонка) и обратный ход (обратная прогонка).

Прямой ход метода прогонки состоит в вычислении прогоночных коэффициентов

i (i =) и i (i =).

При i = 1 эти коэффициенты вычисляются по формулам:

1 = -с 1 / 1 ; 1 = -d 1 / 1 ; 1 = b 1 .

Для i = используются следующие рекуррентные формулы:

i = -с i / i ; i = (d i - a i i-1) / i ; i = b i + a i i-1 .

Прямая прогонка завершается при i = n:

n = (d n - a n n-1) / n ; n = b n + a n n-1 .

Обратный ход метода прогонки позволяет вычислить значения неизвестных. Сначала полагают x n = n . Затем в обратном порядке по формуле (9) определяют значения неизвестных x n -1 , x n -2 , ..., x 1 .

Свойства метода прогонки. Трудоемкость метода прогонки оценивается примерно как 8n арифметических операций, что существенно меньше метода Гаусса. Существование решения системы (8) и его единственность гарантируются при выполнении достаточных условий, задаваемых следующей теоремой.

Теорема . Пусть коэффициенты системы (8) удовлетворяют следующим неравенствам

b k a k +c k ; b k >a k ; k = , где a 1 = 0; b n = 0. Тогда i 0 и i

1 для всех i =

Заметим, что при всех i 0 вычисления по формулам прямой прогонки могут быть доведены до конца (ни один из знаменателей не обратится в нуль). Одновременно все коэффициенты i , такие, что i 1, обеспечивают устойчивость по входным данным этапа обратной прогонки по формуле (9).

Вычислительная математика

Метод деления отрезка пополам является самым простым и надежным способом решения нелинейного уравнения. Пусть из предварительного анализа известно, что корень уравнения (2.1) находится на отрезке , т. е. x*, так, что f(x*) = 0...

Вычислительная математика

Метод Ньютона является наиболее эффективным методом решения нелинейных уравнений. Пусть корень x* , так, что f(a)f(b) < 0. Предполагаем, что функция f(x) непрерывна на отрезке и дважды непрерывно дифференцируема на интервале (a, b). Положим x0 = b...

Вычислительная математика

В этом и следующем разделе рассмотрим модификации метода Ньютона. Как видно из формулы (2.13), метод Ньютона требует для своей реализации вычисления производной, что ограничивает его применение. Метод секущих лишен этого недостатка...

Метод поиска глобального минимума, называемый методом поиска по координатной сетке, является надежным, но применим только для задач малой размерности (n<4). Неправильный выбор начального шага сетки может привести к тому...

Линейное и нелинейное программирование

Итерация 1. Счет итераций k = 0 Итерация 2. Счет итераций k = 1 Поиск завершен 3.3...

Математическое моделирование и численные методы в решении технических задач

Теоретические сведения. Решить дифференциальное уравнение у/=f(x,y) численным методом - это значит для заданной последовательности аргументов х0, х1…, хn и числа у0, не определяя функцию у=F(x), найти такие значения у1, у2,…, уn, что уi=F(xi)(i=1,2,…, n) и F(x0)=y0...

Математическое моделирование при активном эксперименте

Правильным симплексом в пространстве Еn называется множество из n+1 равноудаленных друг от друга точек (вершин симплекса). Отрезок, соединяющий две вершины, называется ребром симплекса...

Математическое программирование

Метод Ньютона, алгоритм Ньютона (также известный как метод касательных) -- это итерационный численный метод нахождения корня (нуля) заданной функции. Чтобы численно решить уравнение f(x)=0 методом простой итерации...

Метод вращений решения СЛАУ

Метод геометрических преобразований при решении геометрических задач на построение

Рассмотрим ещё одно геометрическое преобразование - инверсию, которая даёт возможность решить ряд сравнительно сложных задач на построение, трудно поддающихся решению с помощью других рассмотренных нами приёмов...

Решение параболических уравнений

Рассмотрим частный случай задачи, поставленной в предыдущем разделе. В области найти решение уравнения с граничными условиями и начальным условием. Рассмотрим устойчивую вычислительную схему...

Система дифференциальных уравнений с постоянными коэффициентами

До сих пор мы занимались решением одного линейного уравнения с постоянными коэффициентами. Оказывается, однако, что весьма общую систему линейных уравнений с постоянными коэффициентами можно в некотором смысле свести к одному уравнению...

Системный анализ групп преобразований состояний кубика Рубика

CFOP - это название четырёх стадий сборки(рисунок 3.2): Cross, F2L, OLL, PLL: 1) Cross - сборка креста...

Численные методы линейной алгебры

Метод прогонки представляет собой простой и эффективный алгоритм решения систем линейных алгебраических уравнений с трехдиагональными матрицами коэффициентов следующего вида (8) Системы такого вида часто возникают при решении различных...

Численные методы решения трансцендентных уравнений

Пусть уравнение (1) имеет корень на отрезке , причем f (x) и f "(x) непрерывны и сохраняют постоянные знаки на всем интервале . Геометрический смысл метода Ньютона состоит в том, что дуга кривой y = f(x) заменяется касательной...

Для решения систем алгебраических уравнений, которые могут быть представлены в виде (31), разработан специальный метод, называемый методом прогонки. Решение системы (31) ищется в виде

Приведём первое уравнение системы (31) к виду (32):

				y 1+	−f 0

Сравнивая уравнения (33) и (34) получим

α 0=			β 0 = −

Рассматривая остальные уравнения системы (31) получим общие рекуррентные формулы для коэффициентов α i иβ i .

				; β i =		− 1 Ai − fi	(i = 1,2,..,n ).
			− α i− 1 A i
						− α i− 1 A i

Запишем систему уравнений, состоящую из последнего уравнения системы (31) и уравнения (32) для i = n-1 .

A ny n− 1 − C ny n= f n,

y n − 1= α n − 1y n + β n − 1(37)

Решая систему (37) находим выражение для y n :

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

	2Y 1

2 +Y 3

2Y 3 -Y

Y 3 -Y

Матрица А для этой системы имеет следующий вид

Прямой ход метода прогонки

С0 =1; B0 =1; f0 =-2

−2

; β i

β i− 1 A i

− f i

(i = 1,2,..,n ).

− α i− 1 A i

C i− α i− 1 A i

Реализация метода прогонки в среде программы MS Excel Постановка задачи

Рассмотрим процедуру применения этой методики для решения конкретной краевой задачи. Определим конкретную форму уравнения

(1), задав формулы для вычисления его коэффициентов:

p(x) =	−2			; q(x) =	− 12		f (x) =	3x + 1
	2x +
					(2x + 1)			(2x + 1)
и граничные условия
x0 = 2, xk = 6 , y(2)= Y0 = 4							и y(6) = Yk

Запишем рассматриваемый пример при n равном 5. Таким образом, число узлов сетки равно 6, а формат системы соответствует

Как уже отмечено выше, в рассматриваемом нами случае системы (30), если следовать традиционной записи, использованной в (31), значениеА 0 = 0, С 0 =-1, а значениеВ 0 =0 . Аналогично для последнего уравнения имеем значениеА n = 0 иС n =-1, В n =0 .

Рассмотрим последовательность шагов решения на примере уравнения (20) с учетом (32), (33), приведенных выше.

Для того чтобы обеспечить в дальнейшем наглядность и понятность вычислений, заполним таблицу значениями функций p(x), q(x) иf(x), вычисленными в узловых точках приn=5 . Для определения значенияh выполним на листе Excel следующие операции (рис.6.3):

▬ в ячейки А1, С1, Е1 иG1 введём комментарии:"Х 0 =", "Х k =", "n=" и"h=" ,

▬ в ячейку В1 введем значение аргументаХ 0 равное 2,

▬ в ячейку D1 введем значение аргументаХ k равное 6,

▬ в ячейку F1 введем значение аргументаn равное 5,

▬ в ячейку H1 введем формулу "=(D1-B1)/F1" 2 , определяющую значение шага между узлами формируемой сетки как

h = x k− n x 0.

▬ В ячейках второй строки таблицы оформим заголовок таблицы так, как это показано на рис. 6.3.

Определив основные параметры таблицы, заполним столбцы значениями в соответствии с заголовком таблицы, показанным на рис. 6.3. Для этого выполним следующие действия:

1. В ячейки А3:А8 введём индексы строк. Для этого в ячейкуА3 введём цифру0 – индекс первого узла. ПереводимУМ 3 в правый нижний угол ячейкиА3 ,ФЛКМ и, зафиксировав клавишуCtrl , протянемУМ от ячейкиА3 до ячейкиА8 .

2. В ячейку B3 вводим ссылку на ячейку с начальным значением

аргумента Х 0 : "=В1". Значение ссылки формируется, если

2 ) Формулы вводятся в ячейки таблиц, начиная с символа “=” (равно). Двойные кавычки использованы в тексте для выделения формулы. Вводить их в ячейки таблицы не нужно.

3 ) Терминология и сокращения, используемые в тексте методических указаний, приведены в начальном разделе методических указаний к первой лабораторной работе:.

подвести УМ к ячейке, на которую делается ссылка и сделать

3. Заполняем ячейки столбца В , выполняя вычисление значений аргументах в соответствии с формулой

xi + 1 = xi + h (i= 0,1, ... , n− 1).

Для этого в ячейку B4 вводим формулу"=В3+$H$1", которую протягиваем до ячейкиB8 , в которой достигается значение равное значениюx n =Х k . (Для формирования абсолютной ссылки на ячейкуН1 послеЩЛК по ячейкеН1 следует нажать функциональную клавишуF4 ).

4. В ячейках от C3 доC8 вычисляем значения вспомогательной

функции 1/(2 х i + 1) , входящей в знаменатели функцийp(x), q(x) иf(x) . Вводим вC3 формулу"=1/(2*B3+1)" и протягиваем эту формулу до ячейкиC8;

5. В ячейки D3 ,E3 иF3 записываем формулы, соответствующие (32), для вычисления значений функцийp(x), q(x) иf(x). Запись этих формул при вводе их в ячейки таблицы имеет следующий вид:"=- 2*C3" ,"= -12*C3*C3" и"=(3*B3+1)*C3*C3" соответственно.

При протягивании этих формул по столбцам D, Е иF до восьмой строки таблица заполняется так, как показано на рис. 6.4.

коэффициентов A i , C i , B i иF i в соответствии с форматом системы уравнений (30). В ячейкиG3, H3, I3 записываем значения,

определяемые форматом первого уравнения системы (30): A 0 =0, C 0 =-1, В 0 =0. В ячейкуJ3 записываем ссылку на ячейкуJ1, в которой записано начальное значениеF 0 =Y 0 :A i = 1 − p(xi ) h 2

для вычисления коэффициента A 1 . После чего протягиваем эту формулу доячейки G7 .

9. Аналогично в ячейку Н4 вводим формулу для вычисления

коэффициента С 1 : "2-Е4*$H$1*$H$1", а в ячейкуI4 вводим формулу для вычисления коэффициентаB 1 B : "1+D4*$H$1/2",

реализуя соответствующие формулы

		− q(xi ) h2 ; Bi = 1 + p(xi )

Протягиваем эти формулы до ячеек Н7 иI7 .

10. В ячейках столбца J формируем вектор правых частей системы

уравнений (30). В ячейку J4 вводим формулу“=F4*$H$1*$H$1”, соответствующую формулеF i = f i h 2 . Протягиваем эту формулу до ячейкиJ7. В результате получаем таблицу, показанную на рис. 6.5. Следует отметить, что в столбцахG, H, I иJ этой таблицы записаны элементы матрицы, решаемой системы уравнений (30).

11. Используя вычисленные значения коэффициентов A i , C i , B i иF i , находим в соответствии с формулами (37) и (38) значения

коэффициентов α i иβ i . В ячейкуK3 запишем формулу для вычисленияα 0 : "=I3/H3", а в ячейкуL3 формулу для вычисленияβ 0 .: "=-J3/H3". И далее в ячейкиK4 иL4 вводим формулы, соответствующие (38), для вычисления коэффициентов

Назначение . Данный сервис предназначен для решения задач динамического программирования методами прямой и обратной прогонки в онлайн режиме (см. пример решения задачи оптимального распределения инвестиций).

Инструкция . Выберите количество объектов и количество групп возможных вариантов, нажмите Далее. В новом окне выберите метод прогонки .

Количество объектов 2 3 4 5 6 7 8 9 10 Количество вариантов 2 3 4 5 6 7 8 9 10

Пример №1 . Решить задачу методом динамического программирования в прямом и обратном времени для целевой функции, заданной таблично.
F(x 1 ,x 2 ,x 3) = f 1 (x 1) + f 2 (x 2) + f 3 (x 3) → max
x 1 + 2x 2 + 2x 3 ≤ 5

X	0	1	2	3	4	5
f 1 (x 1)	6	7	11	12	15	16
f 2 (x 2)	9	11	13	15
f 3 (x 3)	8	12	14	16

Решение.
I этап. Условная оптимизация . f 1 (L) = max(f 1); 0 ≤ x 1 ≤ 5; x 1 = 0,1,2,3,4,5.
f 1 (0) = max = 6
f 1 (1) = max = 7
f 1 (2) = max = 11
f 1 (3) = max = 12
f 1 (4) = max = 15
f 1 (5) = max = 16
Таблица 1 – Расчет значения функции f 1 (L)

L	0	1	2	3	4	5
f 1 (L)	6	7	11	12	15	16
x 1	0	1	2	3	4	5

f 2 (L) = max; 0 ≤ x 2 ≤ 5; x 2 = 0,1,2,3,4,5.
f 2 (0) = max = 15
f 2 (1) = max = 16
f 2 (2) = max = 20
f 2 (3) = max = 21
f 2 (4) = max = 24
f 2 (5) = max = 25
Таблица 2 – Расчет значения функции f 2 (L)

L	0	1	2	3	4	5
f 2 (L)	15	16	20	21	24	25
x 2	0	0	0	0	0	0

f 3 (L) = max; 0 ≤ x 3 ≤ 5; x 3 = 0,1,2,3,4,5.
f 3 (0) = max = 23
f 3 (1) = max = 24
f 3 (2) = max = 28
f 3 (3) = max = 29
f 3 (4) = max = 32
f 3 (5) = max = 33
Таблица 3 – Расчет значения функции f 3 (L)

L	0	1	2	3	4	5
f 3 (L)	23	24	28	29	32	33
x 3	0	0	0	0	0	0

II этап. Безусловная оптимизация .
Таким образом, максимум f 3 (5) = 33
При этом x 3 = 0, так как f 3 (5) = 33 достигается при х 3 =0 (см. таблицу 3).
Остальные x распределяются следующим образом:
L = 5 - 2 * 0 = 5
f 2 (5) = 25 достигается при х 2 = 0 (см. таблицу 2).
L = 5 - 2 * 0 = 5
f 1 (5) = 16 достигается при х 1 = 5 (см. таблицу 1).
L = 5 - 1 * 5 = 0
В итоге наилучший вариант достигается при значениях: x 1 = 5, x 2 = 0, x 3 = 0

Пример №2 . Рассмотрим задачу об оптимальном размещении капитала K = nh в m различных независимых фондах (банки, организации, фирма и т.д.), для которых известна ожидаемая прибыль f i при капиталовложениях x i = ih, i = 1..n. Здесь n – количество дискретных приращений h (дискрет), на которые разбит капитал К.
Пусть такие данные имеются по четырем (m=4) фондам для h = 1 млн. руб., n = 6

Решение.
I этап. Условная оптимизация.
1-й шаг: k = 4.
Предположим, что все средства в количестве x 4 = 6 отданы 4-у предприятию. В этом случае максимальный доход, как это видно из таблицы 1*, составит 0.56, следовательно:
F 4 (c 4) = g 4 (x 4)
Таблица 1.

0	x 1	0	1	2	3	4	5	6
x 4	f 0 (x 0) / F 4 (x 4)	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0	0
1	0.2	0	0	0	0	0	0.2	0
2	0.33	0	0	0	0	0.33	0	0
3	0.42	0	0	0	0.42	0	0	0
4	0.48	0	0	0.48	0	0	0	0
5	0.53	0	0.53	0	0	0	0	0
6	0.56	0.56*	0	0	0	0	0	0

Таблица 1*.

c 1	0	1	2	3	4	5	6
F 0 (c 1)	0	0.2	0.33	0.42	0.48	0.53	0.56
x 1	0	1	2	3	4	5	6

2-й шаг: k = 3.

F 3 (c 3) = max [ g 3 (x 3) + F 4 (c 3 - x 3)]
Таблица 2.

0	x 2	0	1	2	3	4	5	6
x 3	f 3 (x 3) / F 3 (x 3)	0	0.2	0.33	0.42	0.48	0.53	0.56
0	0	0	0.2*	0.33	0.42	0.48	0.53	0.56
1	0.15	0.15	0.35*	0.48*	0.57	0.63	0.68	0
2	0.25	0.25	0.45	0.58	0.67	0.73	0	0
3	0.4	0.4	0.6*	0.73*	0.82	0	0	0
4	0.5	0.5	0.7	0.83*	0	0	0	0
5	0.62	0.62	0.82	0	0	0	0	0
6	0.73	0.73	0	0	0	0	0	0

Заполняем таблицу 2*. Для этого на каждой северо-восточной диагонали находим наибольшее число, которое отмечаем звездочкой и указываем соответствующее значение x 2 .
Таблица 2*.

c 2	0	1	2	3	4	5	6
F 3 (c 2)	0	0.2	0.35	0.48	0.6	0.73	0.83
x 2	0	0	1	1	3	3	4

3-й шаг: k = 2.
Определяем оптимальную стратегию при распределении средств между остальными предприятиями. При этом рекуррентное соотношение Беллмана имеет вид:
F 2 (c 2) = max [ g 2 (x 2) + F 3 (c 2 - x 2)]
Таблица 3.

0	x 3	0	1	2	3	4	5	6
x 2	f 4 (x 4) / F 2 (x 2)	0	0.2	0.35	0.48	0.6	0.73	0.83
0	0	0	0.2	0.35	0.48	0.6	0.73	0.83
1	0.25	0.25*	0.45*	0.6	0.73	0.85	0.98	0
2	0.41	0.41	0.61*	0.76*	0.89	1.01	0	0
3	0.55	0.55	0.75	0.9*	1.03*	0	0	0
4	0.65	0.65	0.85	1	0	0	0	0
5	0.75	0.75	0.95	0	0	0	0	0
6	0.8	0.8	0	0	0	0	0	0

Заполняем таблицу 3*. Для этого на каждой северо-восточной диагонали находим наибольшее число, которое отмечаем звездочкой и указываем соответствующее значение x 3 .
Таблица 3*.

c 3	0	1	2	3	4	5	6
F 4 (c 3)	0	0.25	0.45	0.61	0.76	0.9	1.03
x 3	0	1	1	2	2	3	3

4-й шаг: k = 1.
Определяем оптимальную стратегию при распределении средств между остальными предприятиями. При этом рекуррентное соотношение Беллмана имеет вид:
F 1 (c 1) = max [ g 1 (x 1) + F 2 (c 1 - x 1)]
Таблица 4.

0	x 4	0	1	2	3	4	5	6
x 1	f 5 (x 5) / F 1 (x 1)	0	0.25	0.45	0.61	0.76	0.9	1.03
0	0	0	0.25	0.45	0.61	0.76	0.9	1.03
1	0.28	0.28*	0.53*	0.73*	0.89	1.04	1.18	0
2	0.45	0.45	0.7	0.9	1.06	1.21	0	0
3	0.65	0.65	0.9*	1.1*	1.26*	0	0	0
4	0.78	0.78	1.03	1.23	0	0	0	0
5	0.9	0.9	1.15	0	0	0	0	0
6	1.02	1.02	0	0	0	0	0	0

Заполняем таблицу 4*. Для этого на каждой северо-восточной диагонали находим наибольшее число, которое отмечаем звездочкой и указываем соответствующее значение x 4 .
Таблица 4*.

c 4	0	1	2	3	4	5	6
F 5 (c 4)	0	0.28	0.53	0.73	0.9	1.1	1.26
x 4	0	1	1	1	3	3	3

II этап. Безусловная оптимизация.
1-й шаг: k = 1.
По данным таблицы 4* максимальный доход при распределении 6 между предприятиями составляет c 1 = 6, F 1 (6) = 1.26. При этом 1-му предприятию нужно выделить x 1 = 3.
2-й шаг: k = 2.

c 2 = c 1 - x 1 = 6 - 3 = 3.
По данным таблицы 3* максимальный доход при распределении 3 между предприятиями составляет c 2 = 3, F 2 (3) = 0.61. При этом 2-му предприятию нужно выделить x 2 = 2.
3-й шаг: k = 3.
Определим величину оставшихся денежных средств, приходящихся на долю остальных предприятий.
c 3 = c 2 - x 2 = 3 - 2 = 1.
По данным таблицы 2* максимальный доход при распределении 1 между предприятиями составляет c 3 = 1, F 3 (1) = 0.2. При этом 3-му предприятию нужно выделить x 3 = 0.
4-й шаг: k = 4.
Определим величину оставшихся денежных средств, приходящихся на долю остальных предприятий.
c 4 = c 3 - x 3 = 1 - 0 = 1.
По данным таблицы 1* максимальный доход при распределении 1 между предприятиями составляет c 4 = 1, F 4 (1) = 0.20. При этом 4-му предприятию нужно выделить x 4 = 1.
Таким образом, оптимальный план инвестирования предприятия:
x 1 = 3
x 2 = 2
x 3 = 0
x 4 = 1
который обеспечит максимальный доход, равный: F(6) = g 1 (3) + g 2 (2) + g 3 (0) + g 4 (1) = 0.65 + 0.41 + 0 + 0.20 = 1.26.

Данный метод также является модификацией метода Гаусса для частного случая разреженных систем - систем с матрицей трехдиагонального типа (краевая задача ДУ).

Каноническая форма их записи

(1.6)

или в развернутом виде:

(1.7)

При этом, как правило, все коэффициенты b i  0.

Метод реализуется в два этапа - прямым и обратным ходами.

Прямой ход . Каждое неизвестное x i выражается через x i +1

(x i = A i  x i +1 + B i для i = 1,2, ..., n – 1) (1.8)

посредством прогоночных коэффициентов A i и B i . Определим алгоритм их вычисления.

Из первого уравнения системы (1.7) находим x 1:

.

Из уравнения (1.8) при i = 1 x 1 = A 1  x 2 + B 1 . Следовательно,

и согласно уравнению (1.8) при i = 2 x 2 = A 2 x 3 + B 2 , следовательно:

,

где е 2 = а 2 А 1 + b 2 .

Ориентируясь на соотношения индексов при коэффициентах уравнений (1.9) и (1.9*), можно получить эти соотношения для общего случая:

,

где е i = а i  А i –1 + b i (i = 2,3, ..., n – 1) . (1.10)

Обратный ход. Из последнего уравнения системы (1.7) с использованием данных выражения (1.8) при i = n – 1

.

При реализации метода прогонки нужно учитывать, что при условии

(1.12)

или хотя бы для одного b i имеет место строгое неравенство (1.12), деление на «0» исключается и система имеет единственное решение.

Заметим, что условие (1.12) является достаточным, но не необходимым. В ряде случаев для хорошо обусловленных систем (1.7) метод прогонки может быть устойчивым и при несоблюдении условия (1.12).

Схема алгоритма метода прогонки может иметь вид, представленный на рисунке 1.2.

Рисунок 1.2 - Блок-схема метода прогонки

Итерационные методы решения слау

Достоинством итерационных методов является их применимость к плохо обусловленным системам и системам высоких порядков, самоисправляемость и простота реализации на ЭВМ. Итерационные методы для начала вычисления требуют задания какого-либо начального приближения к искомому решению.

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

Для применения метода итераций исходную систему необходимо привести к итерационному виду

(1.13)

и затем итерационный процесс выполнить по рекуррентным формулам:

, k = 0, 1, 2, ... . (1.13*)

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

Для сходимости метода (1.13*) необходимо и достаточно, чтобы | i (G )| < 1, где  i (G ) - все собственные значения матрицы G . Сходимость будет и в случае, если ||G || < 1, ибо | i (G )| <  ||G || ( - любой).

Символ ||...|| означает норму матрицы. При определении ее величины чаще всего останавливаются на проверке двух условий:

||G || =
или ||G || =
, (1.14)

где
. Сходимость гарантирована также, если исходная матрицаА имеет диагональное преобладание, т. е.

. (1.15)

Когда условия (1.14) или (1.15) выполняются, метод итерации сходится при любом начальном приближении
. Чаще всего вектор
берут или нулевым, или единичным, или сам векториз системы (1.13).

Если выполняется условие (1.15), тогда преобразование к итерационному виду (1.13) можно осуществить просто, решая каждое i -е уравнение системы (1) относительно x i по следующим рекуррентным формулам:

g ij = − a ij / a ii ; g ii = 0; f i = b i / a ii , (1.15*)

т. е.
.

Если же в матрице А нет диагонального преобладания, его нужно добиться посредством каких-либо ее линейных преобразований, не нарушающих их равносильности.