Численные методы

34

Размещено на http://www.allbest.ru/

КАЗАНСКИЙ ГОСУДАРСТВЕННЫЙ АРХИТЕКТУРНО-СТРОИТЕЛЬНЫЙ УНИВЕРСИТЕТ

Кафедра прикладной математики

МЕТОДИЧЕСКИЕ УКАЗАНИЯ

по курсу "Информатика"

для самостоятельной работы студентов

всех специальностей

ЧИСЛЕННЫЕ МЕТОДЫ

ЧАСТЬ 1

Казань

2008

Составители: Ф.Г. Ахмадиев, Ф.Г. Габбасов, И.Н. Гатауллин, Р.Ф. Гиззятов, Р.И. Ибятов, Х.Г. Киямов.

УДК 621.313: 518.6

Методические указания по курсу "Информатика" для самостоятельной работы студентов всех специальностей. Численные методы. Часть 1. /Казанский государственный архитектурно-строительный университет. Сост.: Ф.Г. Ахмадиев, Ф.Г. Габбасов, И.Н. Гатауллин, Р.Ф. Гиззятов, Р.И. Ибятов, Х.Г. Киямов. Казань, 2008. -35 с.

Методические указания состоят из двух частей и предназначены для самостоятельной работы студентов всех специальностей 2-го курса дневного и заочного отделений. В данной работе приводятся численные методы решения нелинейных уравнений, систем линейных и нелинейных алгебраических уравнений, дифференциальных уравнений, определенных интегралов, методы аппроксимации дискретных функций и методы решения задач линейного программирования.

Табл. 8, библиогр. назв. 6.

Рецензент - Р.Б. Салимов, доктор физ.-мат. наук, профессор

Казанский государственный

архитектурно-строительный

университет, 2008г.

1. Численное решение нелинейных уравнений

Задана непрерывная функция F(x). Требуется определить корни уравнения F(x)=0.

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

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

Уравнения, содержащие другие функции (тригонометрические, показательные, логарифмические и др.) называются трансцендентными.

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

а) отыскания приближенного значения корня, или содержащего его отрезка;

б) уточнения значения до некоторой степени точности.

Приближенное значение корня (начальное приближение) может быть найдено различными способами из физических соображений, из решения аналогичной задачи при других исходных данных, с помощью графических методов. Если такие простые оценки исходного приближения произвести не удается, то находят две близко расположенные точки a и b, в которых непрерывная функция F(x) принимает значения разных знаков, т.е. F(a)*F(b)<0. В этом случае между точками a и b есть, по крайней мере, одна точка, в которой F(x)=0. В качестве начального приближения первой итерации x₀ можно принять середину отрезка [a, b], т.е. x₀=(a+ b)/2.

Итерационный процесс состоит в последовательном уточнении x₀. Каждый такой шаг называется итерацией. В результате итераций находятся последовательности приближенных значений корня x₀, x₁, ... , x_n. Если эта последовательность с ростом значения n приближается к истинному значению корня, то итерационный процесс сходится.

1.1 Метод деления отрезка пополам

Допустим, что мы нашли отрезок [a, b], в котором расположено искомое значение корня x = c, т.е. a<c<b.

Пусть для определенности F(a)<0, F(b)>0 (см. рис. 1.1). В качестве начального приближения корня x₀ принимается середина этого отрезка, т.е. x₀ = (a + b)/2. Далее исследуем значение функции F(x) на концах отрезков [a,x₀] и [x₀,b]. Тот из них, на концах которого F(x) принимает значения разных знаков, содержит искомый корень. Поэтому его принимаем в качестве нового отрезка. Вторую половину отрезка [a, b] отбрасываем. В качестве первой итерации корня принимаем середину нового отрезка и т. д.

y

y=F(x)

F(b)

a b x

F(a) x₀=(a+b)/2

Рис. 1.1 Метод деления отрезка пополам.

Таким образом, после каждой итерации отрезок, на котором расположен корень, уменьшается вдвое, т.е. после n итераций он сокращается в 2ⁿ раз.

Поскольку в рассматриваемом случае F(x₀)<0, то x₀<c<b, и рассматриваем отрезок [x₀,b]. Следующее приближение: x₁=(x₀+b)/2 и т.д. Итерационный процесс продолжаем до тех пор, пока значение функции F(x) после n-й итерации не станет меньшим по модулю некоторого заданного малого числа , т.е. F(x_n)<. Можно также оценивать длину полученного отрезка, если она становится меньше допустимой погрешности, то счет прекращается.

Пример: Найти решение уравнения x³+x-1=0 c точностью =0.01 методом деления отрезка пополам.

Решение: Данное уравнение представим в виде x³=-x+1. Корнем данного уравнения является точка пересечения графиков функций y=x³ и y=-x+1 (рис.1.2). Искомый корень находится между точками a=0 и b=1. Функция F(x)=x³+x-1 на концах отрезка [0,1] принимает значения разных знаков F(a)F(b)<0.

В точках 0; 0.5; 1 заданная функция принимает значения -1; -0,375 и 1, следовательно, корень находится в интервале [0,5;1] (т.е. на концах этого интервала F(x) принимает значения разных знаков). Далее в точках 0,5; 0.75; 1 функция принимает значения -0,375; 0,171875; 1 и следовательно корень находится в интервале [0,5;0,75].



Рис. 1.2

Вычисления производятся до достижения заданной точности

x_i+1-x_i=0,6875-0,679688=0,007812<0.01

и оформляются в виде таблицы 1.1. Приближенным решением данного уравнения является x=0,683594.

Таблица 1.1

a	F(a)	x	F(x)	b	F(b)
0	- 1	0,5	- 0,375	1	+ 1
0,5	- 0,375	0,75	+ 0,171875	1	+ 1
0,5	- 0,375	0,625	- 0,13086	0,75	+ 0,171875
0,625	- 0,13086	0,6875	+ 0,012451	0,75	+ 0,171875
0,625	- 0,13086	0,65625	- 0,06113	0,6875	+ 0,012451
0,65625	- 0,06113	0,671875	- 0,02483	0,6875	+ 0,012451
0,671875	- 0,02483	0,679688	- 0,00631	0,6875	+ 0,012451
0,679688	- 0,00631	0,683594	+ 0,003038	0,6875	+ 0,012451

На рис. 1.3 приведена программа решения данного уравнения методом деления отрезка пополам.

CLS

REM LR-1-1, m=13, n=5

DEF FNF(X) = X^3+X-1

1 INPUT A, B, E

YA= FNF(A): YB=FNF(B)

IF YA*YB>0 THEN 1

2 X =(A+B)/2: Y=FNF(X)

PRINT X, Y

IF YA*Y<0 THEN B=X ELSE A=X

IF (B-A)>E THEN 2

END

Рис.1.3. Пример программы нахождения корней уравнения методом деления отрезка пополам.

1.2 Метод Ньютона (метод касательных)

Суть метода состоит в том, что на k-й итерации в точке (x_k, F(x_k)) строится касательная к кривой y=F(x) и ищется точка пересечения касательной с осью абсцисс. При этом необязательно задавать отрезок [a, b], содержащий корень уравнения, а достаточно найти лишь некоторое начальное приближение корня x=x₀ (рис. 1.4). Если задан интервал изоляции корня [a,b], то за начальное приближение x₀ принимается тот конец отрезка, на котором

F(x₀)·F(x₀)> 0.

Уравнение касательной, проведенной к кривой y=F(x) в точке M₀ с координатами x₀ и F(x₀), имеет вид:

y - F(x₀) = F(x₀)·(x-x₀). (1.1)

y

y=F(x)

F(x₀) М₀

0 x₂ x₁ x₀ x

Рис. 1.4. Метод касательных.

За следующее приближение корня x₁ примем абсциссу точки пересечения касательной с ocью оx:

x₁ =x₀ - F(x₀) / F(x₀). (1.2)

При этом необходимо, чтобы F(x₀) не равнялся нулю:

F(x₀)0

Аналогично могут быть найдены и следующие приближения, как точки пересечения с осью абсцисс касательных, проведенных в точках M₁, M₂ и т.д. Формула для n+1-го приближения имеет вид:

x_n+1 = x_n - F(x_n)/F(x_n). (1.3)

Для завершения итерационного процесса можно использовать условие F(x_n)< , или условие близости двух последних приближений: x_n+1-x_n<.

Объем вычислений в методе Ньютона больше, чем в других методах, поскольку приходится находить значение не только функции F(x), но и ее производной. Однако скорость сходимости здесь значительно выше.

Пример: Решить уравнение F(x)=x³+x-1=0 на отрезке [0;1] методом Ньютона c точностью =0.01.

Решение: Определим первые и вторые производные заданной функции: F(x)=3x²+1; F(x)=6x. Вычислим значения функции F(x) на концах заданного интервала F(0)=-1; F(1)=1. Так как F(1)·F(1)=1·6>0, за начальное приближение корня можно принять x=1. Находим первое приближение:

x₁=x₀-F(x₀)/F(x₀)=x₀-(x₀³+x₀-1)/(3x₀²+1)=1-(1³+1-1)/(3·1²+1)=0,75

Аналогично находится второе приближение:

x₂=x₁ - F(x₁)/F(x₁)=x₁-(x₁³+x₁-1)/(3x₁²+1)=

=0,75-(0,75³+0,75-1)/(3·0,75²+1)=0,686047

Аналогично находится третье приближение:

x₃ =x₂ - F(x₂)/F(x₂)=x₂-(x₂³+x₂-1)/(3x₂²+1)=

=0,686047-(0,686047³+0,686047-1)/(3·0,686047²+1)=0,68234

Так как x₃ - x₂=0,68234-0,686047=0,00371< 0.01, итерационный процесс заканчивается. Таким образом, приближенным решением данного уравнения является x = 0,68234.

На рис. 1.5 приведена программа решения данного уравнения методом Ньютона.

CLS

REM LR-1-2, m=13, n=5

DEF FNF(X)=X^3+X-1

DEF FNP(X)=3*X+1

INPUT X, E

1 X=X- FNF(X)/FNP(X)

PRINT X, FNF(X)

IF ABS(FNF(X)/FNP(X))>E THEN 1

END

Рис. 1.5. Программа нахождения корней методом Ньютона.

1.3 Метод простой итерации

Для использования этого метода исходное нелинейное уравнение F(x)=0 необходимо привести к виду x = (x).

В качестве (x) можно принять функцию (x) =x-F(x)/M, где M неизвестная постоянная величина, которая определяется из условия сходимости метода простой итерации (x)<1. При этом для определения M условие сходимости записывается в следующем виде:

1-F'(x₀)/M <1 или M=1.01· F'(x₀).

Если известно начальное приближение корня x=x₀, подставляя это значение в правую часть уравнения x=(x), получаем новое приближение x₁=(x₀).

Далее подставляя каждый раз новое значение корня в уравнение x=(x), получаем последовательность значений:

x₂=(x₁), x₃=(x₂),..., x_k+1= (x_k)..... k = 1,2,...,n.

Итерационный процесс прекращается, если результаты двух последовательных итераций близки, т.е. x_k+1 - x_k< .

Пример: Решить уравнение F(x)=x³+x-1=0 на отрезке [0;1] методом простой итерации c точностью =0.01.

Решение: Из условия сходимости

1-F(x₀)/M<1 или 1-(3x₀+1)/M<1,

при x₀=1 определяем M>4. Пусть M = 5.

Подставляя каждый раз новое значение корня в уравнение

x_k+1=x_k-(x_k³+x-1)/5,

получаем последовательность значений:

x₁=x₀-(x₀³+x₀-1)/5=1 - (1³+1-1) / 5 = 0,8

x₂ = x₁-(x₁³+x₁-1)/5=0,8 - (0,8³+0,8 -1) / 5 = 0,7376

x₃ =x₂-(x₂³+x₂-1)/5=0,7376 - (0,7376³+0,7376 -1) / 5 = 0,709821

x₄ =x₃ -(x₃³+x₃-1)/5=0,709821- (0,709821³+0,709821-1) / 5 = 0,696329

x₅=x₄-(x₄³+x₄-1)/5=0,696329- (0,696329³+0,696329-1) / 5 = 0,689537

x₅ - x₄ = 0,689537- 0,696329 = 0,00679 < 0.01.

Геометрическая интерпретация метода простой итерации.

Построим графики функций y=x и y=(x). Корнем x^* уравнения x=(x) является абсцисса пересечения кривой y=(x) с прямой y=x ( см. рис. 1.6). Взяв, в качестве начальной точки точку x₀ строим, ломаную линию. Абсциссы вершин этой ломаной представляют собой последовательные приближения корня x^*. Из рисунка видно, что если -1<(x)<0 на отрезке [a, b] (рис. 1.6b), то последовательные приближения x_i+1 = (x_i) колебаются около корня. Если же производная 0<(x)<1 (рис. 1.6.а), то последовательные приближения сходятся монотонно.

На рис.1.7 приведена программа решения данного уравнения методом простой итерации.

CLS

REM LR-1-3, m=13, n=5

DEF FNF(X)= X^3+X-1

INPUT X, E, M

1 X = X - FNF(X)/M

PRINT X, FNF(X)

IF ABS(FNF(X)/M)>E THEN 1

END

Рис.1.7. Программа решения уравнения методом простой итерации.

решение уравнение интеграл функция программирование

2. Методы решения систем линейных алгебраических уравнений

Методы решения систем уравнений:

a₁₁x₁ + a₁₂x₂ + ... + a_1nx_n = b₁

a₂₁x₁ + a₂₂x₂ + ... + a_2nx_n = b₂

................................................ (2.1)

a_n1x₁ + a_n2x₂ + ... + a_nnx_n = b_n

делятся на точные и приближенные.

2.1 Метод Гаусса

Является одним из наиболее распространенных методов решения систем линейных алгебраических уравнений. Этот метод является точным методом. В основе метода Гаусса лежит идея последовательного исключения неизвестных. Рассмотрим систему из трех уравнений с тремя неизвестными:

I: a₁₁x₁ + a₁₂x₂ + a₁₃x₃ = b₁

II: a₂₁x₁ + a₂₂x₂ + a₂₃x₃ = b₂ (2.2)

III: a₃₁x₁ + a₃₂x₂ + a₃₃x₃ = b₃

Система уравнений (2.2) приводится к эквивалентной системе с треугольной матрицей:

I: a₁₁x₁ + a₁₂x₂ + a₁₃x₃ = b₁

II: a₂₂x₂ + a₂₃x₃ = b₂ (2.3)

III: a₃₃x₃ = b₃

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

Процесс приведения системы (2.2) к системе (2.3) называется прямым ходом, а нахождение неизвестных x₁, x₂, x₃ из системы (2.3) называется обратным ходом.

Прямой ход исключения: Исключаем x₁ из уравнений (II) и (III) системы (2.2). Для этого умножаем уравнение (I) на d₁=-a₂₁/a₁₁ и складываем со вторым, затем умножаем на d₂=-a₃₁/a₁₁ и складываем с третьим.

В результате получаем следующую систему:

II: a₂₂x₂ + a₂₃x₃ = b₂

III: a₃₂x₂ + a₃₃x₃ = b₃ (2.4)

Из полученной системы (2.4) исключаем x₂ . Для этого умножая новое уравнение на d₃=-a₃₂/a₂₂ и складываем со вторым уравнением, получим уравнение:

III: a₃₃x₃ = b₃ (2.5)

Взяв из каждой системы (2.2), (2.4) и (2.5) первые уравнения, получим систему уравнений с треугольной матрицей.

Обратный ход: Из уравнения (III) находим x₃=b₃/a₃₃. Из уравнения (II) находим x₂=b₂-a₂₃x₃. Из уравнения (I) находим x₁=b₁-a₁₂x₂-a₁₃x₃. Коэффициенты a₁₁, a₂₂ называются ведущими элементами 1-го и 2-го шагов исключения неизвестных. Они должны быть отличны от нуля. Если они равны нулю, то, меняя местами строки, необходимо на их место вывести ненулевые элементы.

Аналогичным путем методом Гаусса решаются системы n уравнений с n неизвестными.

Пример: Решить систему уравнений методом Гаусса:

x₁ + 4x₂ + 3x₃ = 10

2x₁ + x₂ - x₃ = -1

3x₁ - x₂ +x₃ = 11

Решение: Удалить члены с x₁ из 2-го и 3-го уравнений можно, вычитая из 2-ой строки 1-ую, умноженную на 2, а из 3-й - первую, умноженную на 3:

x₁ + 4x₂ + 3x₃ = 10

-7x₂ - 7x₃ = -21

-13x₂ -8x₃ = -19

2-ая строка делится на -7:

x₁ + 4x₂ +3x₃ = 10

x₂ + x₃ = 3

13x₂ + 8x₃ = 19

Вторая строка умножается на 13 и вычитается из 3-ей:

x₁ + 4x₂ + 3x₃ = 10

x₂ + x₃ = 3

-5x₃ = -20

3-я строка делится на -5:

x₁ + 4x ₂+ 3x₃ = 10

x₂ + x₃ = 3

x₃ = 4

Процедура обратного хода дает исходное решение:

x₃ = 4;

x₂ = 3 - x₃ = -1;

x₁ =10 -4x₂-3x₃ = 10 - 4*(-1) - 3*4=10+4-12=2.

2.2 Метод прогонки

Является частным случаем метода Гаусса и применяется для решения систем уравнений с трех диагональной (ленточной) матрицей. Такая система уравнений записывается в виде:

a_ix_i-1+b_ix_i+c_ix_i+1 = d_i i = 1, 2, 3, ..., n (2.6)

a₁= 0; c_n = 0.

Формула обратного хода записываем в следующем виде:

x_i = U_i x_i+1 + V_i ; i = n, n-1,..,1 (2.7)

Уменьшаем в формуле (2.7) индекс на единицу и подставляем в (2.6):

x_i-1 = U _{i -1}x_i + V_i-1,

a_i (U_i-1x_i + V_i-1) + b_ix_i + c_ix_i+1 = d_i

Приведем подобные и запишем:

(a_iU_i-1 +b_i)x_i =-c_ix_i+1 + d_i -a_iV_i-1,

x_i =-c_i /(a_iU_i-1+ b_i)x_i+1+ (d_i - a_iV_i-1)/(a_iU_i-1 + b_i) (2.8)

сравнивая (2.7) и (2.8), получим:

U_i = -c_i / (b_i + a_iU_i-1);

V_i = (d_i - a_iV_i-1) / (b_i + a_iU_i-1); i = 2, 3, ..., n (2.9)

Поскольку a₁ = 0, то

U₁ = -c₁ / b₁; V₁ = d₁ / b₁. (2.10)

Теперь по формулам (2.9) и (2.10) можно вычислить прогоночные коэффициенты U_i и V_i (i=1,2,3,...,n). Это прямой ход прогонки. Зная прогоночные коэффициенты по формулам (2.7), можно вычислить все x_i; i=n,...,3,2,1 (обратный ход прогонки). Поскольку c_n = 0, то U_n = 0 и x_n = V_n. Далее вычисляем x_n-1, x_n-2, ..., x₂, x₁.

Пример: Решить систему уравнений методом прогонки:

10x₁ + x₂ = m+5

-2x₁ + 9x₂ + x₃ = n+9 m -1

0,1x₂ +4x₃ -x₄ = 4 n+0,1 m -5

-x₃ +8x₄ - x₅ = 40 -n - L

x₅ = L,

где значения m - номер варианта, n - номер группы, L - номер факультета.

Решение: Даны значения a_i; b_i; c_i; d_i; m=0, n=0, L=0; i=1, 2, 3, 4, 5. Их записываем в виде таблицы 2.1.

Таблица 2.1

i	ai	bi	ci	di
1	0	10	1	5
2	-2	9	1	-1
3	0,1	4	-1	-5
4	-1	8	-1	40
5	0	1	0	0

Прямой ход прогонки. По формулам (2.9) и (2.10) определяем прогоночные коэффициенты U_i и V_i (i=1,2,3,4).

U₁=-c₁/b₁=-1/10=-0,1

V₁=d₁/b₁=5/10=0,5

U₂= -c₂ /(b₂ + a₂U₁)=-1/(9+2·0,1)= -0,1087

V₂ = (d₂ - a₂V₁)/(b₂ + a₂U₁)=(-1+2·0,5)/(9+2·0,1)=0

U₃= -c₃ /(b₃ + a₃U₂)=1/(4-0,1·0,1087)= 0,25068

V₃ = (d₃ - a₃V₂)/(b₃ + a₃U₂)=(-5-0,1·0)/( 4-0,1·0,1087)= -1,25341

U₄= -c₄ /(b₄ + a₄U₃)= 1/(8-1·0,25068)= 0,1290436

V₄ = (d₄ - a₄V₃)/(b₄ + a₄U₃)=(40-1·1,25341)/(8-1·0,25068)= 5

U₅= -c₅ /(b₅ + a₅U₄)=0

V₅ = (d₅ - a₅V₄)/(b₅ + a₅U₄)=(0-0·5)/(1+0·0,1290436)= 0

Обратный ход прогонки. По формулам (2.7) вычисляем все x_i; i=4,3,2,1). Поскольку c_n = 0, то x₅ = V₅ = 0.

Далее вычисляем x₄, x₃, x₂, x₁.

x ₄ = U₄ x₅ + V₄ =0,1290436 · 0+5=5

x ₃ = U₃ x₄ + V₃ =0,25068·5-1,25341=0

x₂ = U₂ x₃ + V₂ =-0,1087·0+0=0

x₁ = U₁ x₂ + V₁ =-0,1·0+0,5=0,5

Вычисляем невязки r_i = d_i - a_ix_i-1 - b_ix_i - c_ix_i+1; i=1, 2, 3, 4, 5.

r₁ = d₁ - b₁x₁ - c₁x₂ = 5 -10·0,5 - 1 · 0=0

r₂ = d₂ - a₂x₁ - b₂x₂ - c₂x₃ = -1+2·0,5 - 9·0 - 0=0

r₃ = d₃ - a₃x₂ - b₃x₃ - c₃x₄ = -5-0,1 · 0 -4 · 0 +1 · 5=0

r₄ = d₄ - a₄x₃ - b₄x₄ - c₄x₅ = 40 +1 · 0 -8 · 5 +1 · 0 =0

r₅ = d₅ - a₅x₄ - b₅x₅ = 0 -0 · 5 -1 · 0 = 0

Алгоритм метода прогонки заключается в следующем:

Ввести a_i; b_i; c_i; d_i; i=1, 2, 3, ..., n.

Выполнить прямой ход, т.е. вычислить U_i и V_i; i=1, 2, 3, ..., n.

Выполнить обратный ход прогонки, т.е. вычислить x_i=U_i · x_i+1+V_i;

i=n, n-1,...,1.

Напечатать x_i; i=1, 2, 3, ..., n.

Вычислить невязки r_i = d_i - a_ix_i-1 - b_ix_i - c_ix_i+1; i=1, 2, 3, ..., n.

Напечатать r_i ; i=1, 2, 3, ..., n.

На рис. 2.1 приведена программа решения методом прогонки.

REM LR-2-2, m=13, n=5

DIM A(5), B(5), C(5), D(5), U(5), V(5), X(6), R(5)

DATA 0, 10, 1, 5

DATA -2, 9, 1, -1

DATA 0.1, 4, -1, -5

DATA -1, 8, -1, 40

DATA 0, 1, 0, 0

FOR I =1 TO 5

READ A(I), B(I), C(I), D(I)

U(I) = -C(I) / (A(I)*U(I-1) + B(I))

V(I) =(D(I)-A(I)*V(I-1)) / (A(I)*U(I-1) + B(I))

NEXT I

X(5) = V(5)

FOR I =4 TO 1 STEP -1

X(I) = U(I)*X(I+1) + V(I)

NEXT I

FOR I =1 TO 5

R(I) = D(I)-A(I)*X(I-1)-B(I) *X(I)-C(I)*X(I+1)

PRINT X ; I; = ; X(I); R; I; R(I)

NEXT I

Рис.2.1. Программа решения методом прогонки.

2.3 Метод простой итерации (метод Якоби)

Суть вычислений итерационными методами состоит в следующем: расчет начинается с некоторого заранее выбранного приближения x⁽⁰⁾ (начального приближения). Вычислительный процесс, использующий матрицу А, вектор В, системы (2.1) и x⁽⁰⁾ приводит к новому вектору x⁽¹⁾:

_{i-1 n}

x_i⁽¹⁾ =(b_i - a_ij x_j⁽⁰⁾ - a_ij x_j⁽⁰⁾) / a_ij ;

^{j=1 j=i+1} (2.11)

i=1, 2, 3, ..., n; j =1, 2, 3, ..., n.

Затем процесс повторяется, только вместо x⁽⁰⁾ используется новое значение x⁽¹⁾. На k +1-м шаге итерационного процесса по A,B,X получают:

_{i-1 n}

x_i^(k+1) =(b_i - a_ij x_j^(k) - a_ij x_j^(k)) / a_ij ;

^{j=1 j=i+1} (2.12)

i=1, 2, 3, ..., n; j =1, 2, 3, ..., n.

При выполнении некоторых заранее оговоренных условий процесс сходится при k. Сходимость метода простой итерации обеспечивается при выполн. усл. преобладания диагональных элементов матрицы A, т.е.:

a_ija_ii; i=1, 2, 3, ..., n. (2.13)

^ij

Заданная точность достигается при выполнении условия:

maxx_i^(k+1) - x_i^(k) (2.14)

¹ⁱⁿ

Пример: Преобразовать систему уравнений:

7x₁ + 4x₂ -x₃= 7

2x₁+6x₂+3x₃=-2 (2.15)

-x₁+ x₂ + 4x₃=4

к виду, пригодному для построения итерационного процесса методом Якоби и выполнить три итерации.

Решение: Достаточное условие сходимости (2.13) выполняется, поэтому начальное приближение может быть любым.

a₁₂a₁₃4+1a₁₁7

a₂₁a₂₃2+3a₂₂6

a₃₁a₃₂1+1a₃₃4

В i-ом уравнении все члены, кроме x_i, переносятся в правую часть:

x₁ =(7-4x₂+x₃)/7

x₂ =(-2-2x₁-3x₃)/6 (2.16)

x₃ =(4+x₁-x₂)/4

Задается начальное приближение x⁽⁰⁾=(x₁⁽⁰⁾; x₂⁽⁰⁾; x₃⁽⁰⁾), которое подставляется в правую часть. Обычно x₁⁽⁰⁾=0, x₂⁽⁰⁾=0, x₃⁽⁰⁾=0 и получают результаты первой итерации:

x₁⁽¹⁾ =(7-4·0+0)/7 =1

x₂⁽¹⁾ =(-2-2·0-3·0)/6 =-1/3 = - 0.333

x₃⁽¹⁾ =(4+0-0)/4 =1.

Результаты первой итерации x⁽¹⁾=(x₁⁽¹⁾; x₂⁽¹⁾; x₃⁽¹⁾) подставляют в правую часть и получают результаты второй итерации:

x₁⁽²⁾ =(7-4· (-0.333)+1)/7 = 4/3= 1.333

x₂⁽²⁾ =(-2-2·1-3·1)/6 = -7/6 = - 1.167

x₃⁽²⁾ =(4+1-(-1/3))/4 = 4/3 = 1.333

Результаты второй итерации x⁽²⁾=(x₁⁽²⁾; x₂⁽²⁾; x₃⁽²⁾) подставляют в правую часть и получают результаты третьей итерации:

x₁⁽³⁾ =(7-4· (-1.167)+1.333)/7 = 1.857

x₂⁽³⁾ =(-2-2·1.333-3·1.333)/6 = - 1.444

x₃⁽³⁾ =(4+1.333-(-1.167))/4 = 1.625

Определяют достигнутую точность из условия:

max x_i⁽³⁾ - x_i⁽²⁾ .

¹ⁱ³

x₁⁽³⁾ - x₁⁽²⁾ = 1.857-1.333= 0.524

x₂⁽³⁾ - x₂⁽²⁾ = - 1.444+ 1.167= 0.278

x₃⁽³⁾ - x₃⁽²⁾ = 1.625-1.333= 0.292

2.4 Метод Зейделя

Вычисления в этом методе почти такие же, как и в методе Якоби, с той лишь разницей, что в последнем новые значения x^(k+1) не используются до новой итерации. В методе Зейделя при нахождении k+1-ой компоненты используются уже найденные компоненты этой же итерации с меньшими номерами, т.е. последовательность итераций задается формулой:

_{i-1 n}

x_i^(k+1) =(b_i - a_ij·x_j^(k+1) - a_ij·x_j^(k))/a_ij;

^{j=1 j=i+1} (2.17)

i=1, 2, 3, ..., n; j =1, 2, 3, ..., n.

Сходимость и точность достигаются условиями (2.13) и (2.14).

Пример: Задать итерационный процесс Зейделя для нахождения решений системы уравнений (2.15).

Решение: Достаточное условие сходимости (2.13) выполняется, поэтому начальное приближение может быть любым.

Используя (2.16) получим:

x₁^(k+1) =(7-4x₂^(k) +x₃^(k))/7

x₂^(k+1) =(-2-2x₁^(k+1)-3x₃^(k))/6

x₃^(k+1) =(4+x₁^(k+1) -x₂^(k+1))/4.

После задания начального приближения x⁽⁰⁾=(x₁⁽⁰⁾; x₂⁽⁰⁾; x₃⁽⁰⁾), например, x⁽⁰⁾=(0; 0; 0) выражение для первой итерации имеет вид:

x₁⁽¹⁾ =(7-4x₂⁽⁰⁾ +x₃⁽⁰⁾)/7 =(7-4·0+0)/7 =1

x₂⁽¹⁾ =(-2-2x₁⁽¹⁾-3x₃⁽⁰⁾)/6 =(-2-2·1-3·0)/6 = - 0.667

x₃⁽¹⁾ =(4+x₁⁽¹⁾-x₂⁽¹⁾)/4 =(4+1-(-2/3))/4 =1.417

Результаты первой итерации x⁽¹⁾=(x₁⁽¹⁾; x₂⁽¹⁾; x₃⁽¹⁾) подставляют в правую часть и получают результаты второй итерации:

x₁⁽²⁾ =(7-4· (-0.667)+1.417)/7 = 1.583

x₂⁽²⁾ =(-2-2·1.583-3·1.417)/6 = - 1.569

x₃⁽²⁾ =(4+1.583-(-1.569))/4 = 1.788

Результаты второй итерации x⁽²⁾=(x₁⁽²⁾; x₂⁽²⁾; x₃⁽²⁾) подставляют в правую часть и получают результаты третьей итерации:

x₁⁽³⁾ =(7-4· (-1.1569)+1.788)/7 = 2.152

x₂⁽³⁾ =(-2-2·2.152-3·1.788)/6 = - 1.945

x₃⁽³⁾ =(4+2.152-(-1.945))/4 = 2.024

Точность решения определяют из условия: