- •ВВЕДЕНИЕ
- •ПРИБЛИЖЕННОЕ РЕШЕНИЕ НЕЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ
- •Постановка задачи
- •Приближенные (итерационные) методы решения НАУ
- •Метод деления отрезка пополам (дихотомии).
- •Метод простой итерации
- •Метод релаксации
- •Метод Ньютона (касательных)
- •Метод хорд
- •МЕТОДЫ РЕШЕНИЯ СИСТЕМ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ
- •Постановка задачи
- •Прямые методы решения СЛАУ
- •Метод Крамера
- •Метод обратной матрицы
- •Метод Гаусса
- •Метод прогонки
- •Итерационные методы решения линейных алгебраических систем
- •Метод простой итерации
- •Метод Якоби
- •Метод Гаусса-Зейделя
- •АППРОКСИМАЦИЯ ФУНКЦИЙ
- •Постановка задачи интерполяции
- •Локальная интерполяция
- •Кусочно-постоянная интерполяция
- •Кусочно-линейная интерполяция
- •Кубический интерполяционный сплайн
- •Глобальная интерполяция
- •Полином Лагранжа
- •Подбор эмпирических формул
- •Метод наименьших квадратов
- •ЧИСЛЕННОЕ ИНТЕГРИРОВАНИЕ
- •Постановка задачи
- •Формулы прямоугольников
- •Формула трапеций
- •Формула Симпсона
- •ЧИСЛЕННОЕ РЕШЕНИЕ ОБЫКНОВЕННЫХ ДИФФЕРЕНЦИАЛЬНЫХ УРАВНЕНИЙ
- •Постановка задачи
- •Приближенные методы решения задачи Коши для ОДУ первого порядка
- •Метод Эйлера
- •Модифицированный метод Эйлера
- •Методы Рунге-Кутты
- •Численные методы решения систем ОДУ первого порядка
- •МЕТОД КОНЕЧНЫХ РАЗНОСТЕЙ РЕШЕНИЯ КРАЕВЫХ ЗАДАЧ ДЛЯ ОДУ
- •Постановка задачи
- •Аппроксимация производных
- •ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ И РЕКОМЕНДАЦИИ К ЭКЗАМЕНУ
Данное условие есть не что иное, как условие диагонального преобладания.
Итерационные методы решения линейных алгебраических систем
Метод простой итерации
Преобразуем исходную систему линейных |
уравнений |
|
Ax f |
к эквивалентной системе вида: |
|
|
x α x , |
(2.8) |
где x – искомый вектор, а α и – некоторые новые матрица и
вектор, соответственно. Будем решать (2.8) методом последовательных приближений. В качестве нулевого
приближения можно взять |
x 0 0 . Следующее приближение |
|||
|
i |
|
|
|
находим по рекуррентным формулам |
|
|
||
k 1 |
k |
, |
k 0,1, 2, ... |
(2.9) |
x |
α x |
Такой итерационный процесс будем называть методом простых итераций (МПИ). Так же, как и в случае МПИ для решения нелинейных алгебраических уравнений, метод (2.9) сходится не для любой матрицы α. Достаточным условием сходимости МПИ (2.9) к решению системы (2.8) при любом начальном
векторе x 0 является требование |
|
|
|
|
|
|
|
|
|
|
|
|
n |
||||
|
α |
|
1, где |
|
|
|
α |
|
|
|
max |
|
ij |
|
– |
||
|
|
|
|
|
|
|
|
|
|
||||||||
|
|
|
|
|
|
||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
1 i n |
|
|
|
|
|
норма матрицы α. |
|
|
|
|
|
|
|
|
|
|
|
j 1 |
|||||
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Существует несколько способов построения порождающей матрицы α, для которой выполняется достаточное условие сходимости.
Метод Якоби
Предположим, что диагональные элементы |
матрицы A |
исходной системы не равны нулю ( aii 0 , |
i 1,2,..., m ). |
Разрешим первое уравнение системы относительно x1 , второе
33
относительно x2 и т.д. Получим следующую эквивалентную систему, записанную в скалярном виде:
x |
|
|
1 |
|
f |
|
|
a |
|
x |
|
a |
|
x |
|
|
... a |
|
x |
|
|
|
|
|
|
|||||
|
|
|
|
|
1 |
|
2 |
|
3 |
|
|
m |
|
|
|
|||||||||||||||
1 |
|
a11 |
|
|
12 |
|
13 |
|
|
|
1m |
|
|
|
|
|
|
|||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
x |
|
|
1 |
|
f |
|
a |
|
x |
a |
|
|
x |
|
... a |
|
|
x |
|
|
|
|
|
|||||||
2 |
|
|
|
|
2 |
|
23 |
3 |
2m |
m |
|
|
||||||||||||||||||
|
|
|
a22 |
|
|
|
|
21 1 |
|
|
|
|
|
|
|
. |
(2.10) |
|||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
... |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
xm |
1 |
|
f m am1 x1 am2 x2 ... am,m 1 xm 1 |
|
|
|||||||||||||||||||||||||
|
|
|
|
|
|
|
||||||||||||||||||||||||
|
|
|
|
|
amm |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
Зададим вектор нулевого приближения xi 0 . |
Следующие |
приближение будем вычислять по рекуррентным соотношениям
x1k 1 |
1 |
|
f1 |
a12 x2k a13 x3k ... a1m xmk |
|
||
a |
|
||||||
|
11 |
|
|
|
|
|
|
x2k 1 |
1 |
|
f2 |
a21 x1k a23 x3k ... a2m xmk |
|
||
a22 |
(2.11) |
||||||
|
|
|
|
||||
... |
|
|
|
|
|
|
|
xmk 1 |
1 |
|
|
fm am1 x1k am2 x2k ... am,m 1 xmk 1 |
|
||
amm |
|
|
|||||
|
|
|
|
|
В свернутом виде данную систему можно переписать как
|
|
|
|
m |
|
k 1 |
|
1 |
k |
||
|
|
||||
xi |
|
|
fi aij x j |
||
|
|||||
|
|
aii |
j 1 |
|
|
|
|
|
|
j i |
|
Условием окончания условие maxi xi k 1 xi k 1
, i=1, 2, …, m.
итерационного процесса служит
.
Достаточное условие сходимости. Метод Якоби является вариантом МПИ, в котором
|
|
a |
ij |
, i j |
|
|
fi |
|
|
|
|
|
, i 1, 2, ..., m |
||||
|
|
|
|
|||||
ij |
|
a |
ii |
|
, |
i |
aii |
|
|
0, |
i j |
|
|
|
|||
|
|
|
|
|
|
34
Если для исходной матрицы |
|
A выполнено условие |
|||||
|
|
|
|
m |
|
|
|
диагонального преобладания, т.е. |
|
aii |
|
|
aij |
, |
i 1,2,..., m , то |
|
|
||||||
|
|
|
|
j 1 |
|
|
|
|
|
|
|
i j |
|
|
выполняется условие α 1, т.е. итерационный процесс (2.11)
сходится при любом выборе начального приближения. Если исходная система уравнений не удовлетворяет условию сходимости, то ее приводят к виду с диагональным преобладанием. Выбор начального приближения влияет на количество итераций, необходимых для получения приближенного решения. Чаще всего в качестве начального
0 |
|
|
fi |
|
0 |
|
|
приближения берут xi |
i |
|
|
или |
xi |
0 . |
|
aii |
|||||||
|
|
|
|
|
|
Замечание. Указанное выше условие сходимости является достаточным, т.е. если оно выполняется, то процесс сходится. Но данное условие не является необходимым, процесс может сходиться и при отсутствии диагонального преобладания.
ПРИМЕР 2.5. Решить СЛАУ из Примера 2.3 с помощью метода Якоби с точностью 0,01.
С помощью прямого метода обратной матрицы найдено решение x1 1,038 , x2 0,346 , x2 0,158 .
Найдем решение методом Якоби. Для начала проверим условие диагонального преобладания:
8 4 2
5 3 1
10 2 3
Приводим систему уравнений к виду (2.8):
x |
1 10 4x |
2 |
2x |
3 |
|
|
|
|
|
|
||||||
1 |
|
8 |
|
|
|
|
|
x1 |
1,25 0,5x2 0,25x3 |
|
||||||
|
|
|
|
|
|
|
|
|
|
|
||||||
|
|
|
|
1 5 3x |
|
|
|
|
|
|
|
|||||
x |
2 |
|
|
x |
3 |
|
или |
x |
2 |
1 0,6x 0,2x |
3 |
. |
||||
|
|
5 |
1 |
|
|
|
|
|
|
1 |
|
|||||
|
|
|
|
|
|
|
|
|
|
x3 |
0,4 0,3x1 0,2x2 |
|
||||
x |
|
|
|
1 |
4 3x 2x |
|
|
|
||||||||
|
|
|
|
|
|
|
|
|||||||||
3 |
|
|
2 |
|
|
|
|
|
||||||||
|
|
10 |
|
1 |
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
35
|
Тогда |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
x |
k 1 |
1,25 0,5x k |
0,25x k |
|
|
|
|
|
|
|
|
|
|
|||||||||||||||
1 |
|
|
|
|
|
|
2 |
|
|
|
|
|
3 |
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
x |
k 1 |
1 0,6x k |
0,2x k |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||
|
|
|
|
2 |
|
|
|
|
1 |
|
3 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
x |
k 1 |
0,4 0,3x |
k 0,2x |
k |
|
|
|
|
|
|
|
|
|
|
||||||||||||||
|
|
|
|
3 |
|
|
|
|
|
1 |
|
|
|
|
2 |
|
|
|
|
|
|
|
|
|
xi 0 0 . |
||||
|
В |
качестве |
начального |
|
приближения |
выберем |
|||||||||||||||||||||||
Дальнейшие вычисления оформим в виде таблицы: |
|
|
|
|
|
||||||||||||||||||||||||
|
|
|
Номер |
|
|
|
|
x k |
|
|
x k |
|
|
x k |
|
max |
x k 1 |
x k |
|
||||||||||
|
итерации |
|
|
|
|
1 |
|
|
|
|
|
2 |
|
|
|
|
|
3 |
|
i |
|
i |
i |
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||
|
|
|
|
0 |
|
|
|
|
|
0 |
|
|
|
|
|
0 |
|
|
|
|
|
0 |
|
|
- |
|
|
||
|
|
|
|
1 |
|
|
|
|
|
1.25 |
|
|
|
|
1 |
|
|
|
|
0.4 |
|
|
1.25 |
|
|
||||
|
|
|
|
2 |
|
|
|
|
|
0.65 |
|
|
|
|
0.17 |
|
|
0.225 |
|
|
0.83 |
|
|
||||||
|
|
|
|
3 |
|
|
|
|
1.10875 |
|
|
|
|
0.565 |
|
0.239 |
|
|
0.45875 |
|
|||||||||
|
|
|
|
4 |
|
|
|
|
0.90775 |
|
|
|
|
0.28695 |
|
0.180375 |
|
|
0.27805 |
|
|||||||||
|
|
|
|
5 |
|
|
|
1.061431 |
|
0.419275 |
|
0.185065 |
|
|
0.153681 |
|
|||||||||||||
|
|
|
|
6 |
|
|
|
0.994096 |
|
0.326128 |
|
0.165426 |
|
|
0.093147 |
|
|||||||||||||
|
|
|
|
7 |
|
|
|
1.045579 |
|
0.370457 |
|
0.166997 |
|
|
0.051483 |
|
|||||||||||||
|
|
|
|
8 |
|
|
|
1.023022 |
|
0.339253 |
|
0.160418 |
|
|
0.031204 |
|
|||||||||||||
|
|
|
|
9 |
|
|
|
1.040269 |
|
0.354103 |
|
0.160944 |
|
|
0.017247 |
|
|||||||||||||
|
|
|
|
10 |
|
|
|
1.032712 |
|
|
0.34365 |
|
0.15874 |
|
|
0.010453 |
|
||||||||||||
|
|
|
|
11 |
|
|
|
|
1.03849 |
|
|
|
0.348625 |
|
0.158916 |
|
|
0.005778 |
|
||||||||||
|
|
|
|
|
x |
1 |
|
1,25 |
|
|
|
x 1 |
x 0 |
|
|
|
1,25 |
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||
|
|
|
|
|
1 |
|
|
|
|
|
|
|
x21 |
x20 |
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||
|
Здесь x21 1 |
, max |
|
|
|
|
1 |
1,25 |
0,01 , |
|
|
||||||||||||||||||
|
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|
1 |
0 |
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
0,4 |
|
|
|
|
|
|
|
0,4 |
|
|
|
|
|
|||||||||
|
|
|
|
|
x3 |
|
|
|
|
x3 |
|
x3 |
|
|
|
|
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
x 2 1,25 0,5 1 0,25 0,4 0,65 |
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
x22 1 0,6 1,5 0,2 0,4 0,17 |
, |
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||
x32 0,4 0,3 1,25 0,2 1 0,225 |
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||
|
|
|
x 2 |
x 1 |
|
|
|
0,6 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||
|
|
|
|
1 |
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
|
x22 |
x21 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||
max |
|
|
|
|
0,83 |
0,83 0,01 , |
|
|
|
|
|
|
|
||||||||||||||||
|
|
|
|
2 |
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
|
|
x3 |
x3 |
|
|
|
0,175 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
36
x 3 |
1,25 0,5 0,17 0,25 0,225 1,10875 |
||||||||||
|
1 |
|
|
|
|
|
|
|
|
|
|
x23 |
1 0,6 0,65 0,2 0,225 0,565 |
, |
|||||||||
x33 |
0,4 0,3 0,65 0,2 0,17 0,239 |
|
|||||||||
|
|
x 3 |
x 2 |
|
|
|
0,45675 |
|
|
||
|
|
|
|||||||||
|
|
1 |
|
1 |
|
|
|
|
|||
|
x23 |
|
x22 |
|
|
|
|
|
|||
|
|
|
|
||||||||
max |
|
|
|
|
0,395 |
0,45875 |
0,01, и т.д. |
||||
|
|
3 |
|
2 |
|
|
|
|
|
|
|
|
|
|
|
||||||||
|
|
|
|
0,014 |
|
||||||
|
|
x3 |
|
x3 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Процесс продолжается, пока погрешность не станет меньше 0,01 , что происходит на 11-ой итерации. Следовательно,
приближенное решение имеет вид: x1 1,03849 , x2 0,348625, x3 0,158916 , что с точностью совпадает с решением, полученным по методу обратной матрицы.
При реализации в Excel расчетные формулы для xi 1 , при
условии, что исходные данные введены в лист Excel, как показано ниже,
|
|
A |
B |
C |
D |
|
|
E |
|
|
|
F |
G |
|||
1 |
|
|
|
8 |
4 |
2 |
|
|
|
|
|
|
|
10 |
||
2 |
|
A= |
3 |
5 |
1 |
|
|
|
|
|
|
f= |
5 |
|||
3 |
|
|
|
3 |
-2 |
10 |
|
|
|
|
|
|
|
4 |
||
4 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
5 |
|
номер |
|
k |
|
k |
k |
max |
|
x k 1 |
x k |
|
|
|
||
|
|
|
|
|
|
|||||||||||
|
|
итерации |
|
x |
|
x |
2 |
x3 |
i |
|
i |
i |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
|
1 |
|
|
|
|
|
|
|
|
|
|
||||
6 |
|
0 |
|
0 |
0 |
0 |
|
- |
|
|
|
|
|
|||
7 |
1 |
|
1.25 |
1 |
0.4 |
|
1.25 |
|
|
|
|
|
имеют вид:
x11 =1/$B$1*($G$1-$C$1*C6-$D$1*D6), x21 =1/$C$2*($G$2-$B$2*B6-$D$2*D6), x31 =1/$D$3*($G$3-$B$3*B6-$C$3*C6),
max xi 1 xi 0 {=МАКС(ABS(B8:D8-B7:D7))}.
i
37