книги / Численные методы решения задач строительства. Ч. 1
.pdfx(1) |
0,75 0,125 0 0,5 0 0,75, |
|
1 |
|
|
x2(1) |
1,5 0,333 0 |
0,167 0 1,5, |
x(1) |
0,125 0,25 0 |
0,25 0 1,25. |
3 |
|
|
Далее, подставляя это найденное приближение в систему (3.20), получим 2-е приближение решения системы (вторую итерацию):
(2) |
|
x1 |
0,75 0,125 1,5 0,5 1, 25 1,188, |
x2(2) |
1,5 0,333 0,75 0,167 1, 25 1,958, |
x(2) |
0,125 0, 25 0,75 0, 25 1,5 1,063. |
3 |
|
После новой подстановки будем иметь 3-е приближение:
x(3) |
1,036, |
x(3) |
2,073, |
x(3) |
1,057. |
1 |
|
2 |
|
3 |
|
Аналогично получим 4-ю итерацию:
x(4) |
1,020, |
x(4) |
2,022, |
x(4) |
0,991. |
1 |
|
2 |
|
3 |
|
Проверим выполнение условия «близости» двух итераций, т.е. условие (3.18)
M 4 |
|
|
|
max |
|
x 4 x 3 |
|
|
|
|
|
|
|
||||||
|
|
|
|
i |
|
i |
i |
|
|
max 1,020 1,036 ; 2,022 2,073 ; 0,991 1,057
max 0,016;0,051;0,066 0,066 0,1.
Таким образом, за приближенное решение системы (3.19) с точностью ε = 0,1 принимаем 4-ю итерацию
X (4) {1,020; 2,022; 0,991}.
Чтобы получить решение СЛАУ (3.19) с точностью ε = 0,001, потребуется 8 итераций. Точное решение: х1 = 1;
х2 = 2; х3 = 1.
61
Решение данного примера с использованием электронных таблиц Excel приведено в подразд. 3.6.3.
3.3.2. Метод Гаусса–Зейделя
Метод представляет собой модификацию метода Якоби. Основная идея метода заключается в том, что при вы-
числении (k + 1)-й итерации неизвестное xi(k 1) вычисляется с учетом уже найденных x1(k 1) , x2(k 1) , , xi(k1 1) .
Проиллюстрируем метод для n = 3. Пусть система линейных алгебраических уравнений уже приведена к нормальному виду:
|
|
|
|
|
x1 1 12 x2 13 x3 , |
|
|||||||||||||
|
|
|
|
|
x2 2 21x1 |
23 x3 , |
(3.22) |
||||||||||||
|
|
|
|
|
x |
3 |
|
31 |
x |
32 |
x . |
|
|||||||
|
|
|
|
|
|
3 |
|
|
|
|
1 |
|
|
2 |
|
||||
|
|
Выбираем |
|
произвольное |
|
начальное |
приближение |
||||||||||||
|
|
(0){x 0 , x 0 , x 0 |
} и подставляем в 1-е уравнение систе- |
||||||||||||||||
|
X |
||||||||||||||||||
|
|
1 |
2 |
3 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
мы (3.22): |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
x(1) |
|
|
x(0) |
|
|
x(0) . |
|
|||||||
|
|
|
|
|
1 |
|
1 |
|
|
|
12 |
|
2 |
|
13 |
3 |
|
||
|
|
Полученное 1-е приближение x(1) подставляем во 2-е |
|||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
|
|
уравнение системы (3.22): |
|
|
|
|
|
|
|
|
|
|
|||||||||
|
|
|
|
|
x(1) |
|
2 |
|
21 |
x(1) |
|
23 |
x(0) . |
|
|||||
|
|
|
|
|
2 |
|
|
|
|
1 |
|
3 |
|
||||||
|
|
Используя x(1) , x(1) , находим x(1) |
из 3-го уравнения: |
||||||||||||||||
|
|
|
|
1 |
|
2 |
|
|
|
|
|
|
|
|
3 |
|
|
|
|
x3(1) 3 31x1(1) 32 x2(1) .
Этим заканчивается построение 1-й итерации:
X (1){x11 , x21 , x31 }.
62
Используя значения X (1) , можно таким же способом построить следующие итерации. Итерацию с номером (k + 1) можно представить следующим образом:
x k 1 |
x k x k , |
|
||||||
|
1 |
1 |
12 |
2 |
13 |
3 |
|
|
x2(k 1) |
2 |
21x1(k 1) |
23 x3(k ) , |
(3.23) |
||||
x(k 1) |
x(k 1) x(k 1) . |
|
||||||
|
|
|
|
|
|
|
|
|
|
3 |
3 |
31 |
1 |
|
32 |
2 |
|
|
|
|
Итерационный процесс продолжается до тех пор, пока
два соседних приближения X (k ) , X (k 1) не станут доста-
точно близкими. Критерий близости может быть задан условием (3.18), и если оно выполняется, то за приближенное решение системы (3.22) с точностью принимается (k+1)- я итерация, т.е.
|
|
|
(k 1) . |
(3.24) |
X |
X |
Пример 3.3. Методом Гаусса–Зейделя решить ту же самую систему (3.19), которую решали методом Якоби.
Система, приведенная к нормальному виду:
x1x2x3
0,75 0,125x2 0,5x3 ,
1,5 0,333x1 0,167x3 ,
0,125 0,25x1 0,25x2 .
В качестве нулевого приближения возьмем вектор свободных членов :
x(0) |
0,75, |
x(0) |
1,5, |
x(0) |
1,25. |
1 |
|
2 |
|
3 |
|
Применяя алгоритм Гаусса-Зейделя, последовательно получим
x(1) 0,75 0,125 1,5 0,5 1,25 1,188,
1
x2(1) 1,5 0,333 1,188 0,167 1,25 2,104,x3(1) 0,125 0,25 1,188 0,25 2,104 1,021.
63
(2) |
|
x1 |
0,75 0,125 2,104 0,5 1,021 0,997, |
x2(2) |
1,5 0,333 0,997 0,167 1,021 2,003, и т.д. |
x(2) |
0,125 0, 25 0,997 0, 25 2,003 0,999. |
3 |
|
Точное решение этой системы имеет вид х1 = 1; х2 = 2;
х3 = 1.
Расчетная схема метода Гаусса–Зейделя с использованием электронных таблиц Excel аналогична расчетной схеме метода Якоби, приведенной в подразд. 3.6.1.
3.3.3. Условия сходимости итерационного процесса
Прежде чем применять итерационные методы для решения какой-либо системы, необходимо убедиться, что решение может быть получено, т.е. итерационный процесс сходится к точному решению.
Доказывается теорема [2]: если хотя бы одна из норм матрицы нормальной системы (3.14) меньше единицы, то итерационный процесс сходится к единственному решению. То есть изложенные выше итерационные методы можно использовать для систем, удовлетворяющих одному из следующих условий [6]:
n
1 maxi ij 1
j 1
либо
n
2 maxj ij 1, (3.25)
i 1
либо
|
n |
|
3 |
ij2 |
1. |
i 1
64
А для системы (3.11) итерационный процесс сходится, если элементы матрицы А удовлетворяют условию (3.12), т.е. матрица А является матрицей «с преобладанием диагональных элементов».
Пример 3.4. Показать, что для системы (3.19) примера 3.2 итерационный процесс является сходящимся.
Решение. Матрица системы, приведенной к нормальному виду (3.20), имеет вид
0 |
0,125 |
0,5 |
||
|
0,333 |
0 |
0,167 |
|
|
|
|||
|
0,25 |
0,25 |
0 |
|
|
|
|
|
|
Для проверки достаточного условия сходимости вычислим нормы матрицы :
|
|
|
|
|
1 |
max |
{0,625; 0,5; 0,5} 0,625, |
|
|
|
|||||
|
|
|
|
|
|
i |
|
|
|
|
|
|
|
|
|
|
|
2 |
max |
0,583; |
0,375; 0,667 0,667, |
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
j |
|
|
|
|
|
|
|
3 |
0,1252 0,52 0,3332 |
0,1672 0,252 0,252 0,728. |
||||||
|
|
|
|||||||||||
|
|
|
Достаточное условие сходимости (3.25) итерационного процесса выполнено.
Таким образом, теорема сходимости накладывает жесткие условия на коэффициенты заданной системы уравнений
A X B.
Однако если det A 0, то с помощью конечного числа элементарных преобразований исходную систему всегда можно привести к эквивалентной такой, что условие сходимости (условие преобладания диагональных элементов) (3.12) будет выполнено.
Пример 3.5. Привести систему к виду, пригодному для использования итерационных методов решения:
65
(A) |
x 3x 4x 3, |
|||
|
|
1 |
2 |
3 |
(B) |
2,5x1 |
7x2 |
x3 3,5, |
|
(C) |
4,5x |
2x |
3x 1,5. |
|
|
|
1 |
2 |
3 |
Решение:
1. В уравнении (В) коэффициент при х2 по модулю больше суммы модулей остальных коэффициентов. Принимаем уравнение (В) за 2-е уравнение новой системы:
2,5x1 + 7x2 – x3 = 3,5.
2. Из оставшихся неиспользованных уравнений системы составляем линейно независимые между собой комбинации. За 1-е уравнение новой системы можно взять линейную комбинацию (2С) + (А):
10х1 – х2 + 2х3 = 0.
3. За 3-е уравнение новой системы можно принять линейную комбинацию (2А) – (В), т.е.
–0,5х1 – х2 – 7х3 = 2,5.
Витоге получаем систему линейных алгебраических уравнений, эквивалентную исходной, но «с преобладанием диагональных элементов»:
10x1 x2 2x3 0, |
||||
|
2,5x1 |
7x2 x3 |
3,5, |
|
|
||||
|
0,5x |
x |
7x |
2,5. |
|
1 |
2 |
3 |
|
3.4. Устойчивость решения СЛАУ относительно исходных данных
(или обусловленность задач и вычислений)
Рассмотрим систему линейных алгебраических уравнений
A X B.
66
Будем считать, что det A 0, B 0.
Матрица А и вектор правой части B во многих случаях задаются приближенно. Они получены либо в процессе эксперимента, либо в процессе каких-то промежуточных расчетов, содержащих соответственно погрешности эксперимента либо погрешности округления.
Естественно встает вопрос, как эти погрешности (возмущения) исходных данных влияют на точность решения. Чтобы на него ответить, надо познакомиться с особой характеристикой матриц, которую называют обусловленно-
стью [3].
Замечание. Говорят, что задача, модель или вычисление плохо обусловлены, если они чувствительны к ма-
лым изменениям (возмущениям) входящих в нее величин,
т.е. исходных данных. В противном случае – хорошо обу-
словлены.
Таким образом, обусловленность характеризует устойчивость решения системы относительно исходных данных.
Введем еще одно определение: задача решения СЛАУ является корректной, если решение существует, единственно (det A 0) и непрерывно зависит от исходных данных (матриц А и В), т.е. малым изменениям исходных данных соответствуют малые изменения решения задачи.
Прежде всего оговорим различие между плохо обусловленной задачей и плохо обусловленнымивычислениями.
Если задача плохо обусловлена, то никакие усилия,
потраченные на организацию изощренных вычислений, не могут дать правильный ответ, исключая случайность. С плохо обусловленными задачами можно столкнуться при расчетах стержневых систем методами строительной механики. Например:
67
при расчете рам методом перемещений, если два узла соединены очень жесткой частью конструкции;
при расчете конструкции методом сил, если выбрать основную систему так, что перемещение в устраняемой связи, соответствующее приложенной в ней паре нагрузок, равно или меньше перемещений в других устраненных связях от этой же нагрузки.
Все плохо обусловленные вычисления являются ре-
зультатом применения численно неустойчивых алгоритмов. Например, метод исключения Гаусса без выбора главного элемента может обладать таким недостатком.
У плохо обусловленной матрицы обратная матрица является неустойчивой, т.е. элементы обратной матрицы значительно изменяются при малом изменении элементов исходной матрицы.
Пример 3.7. Рассмотрим плохо обусловленную систе-
му, записанную в матричном виде:
5 7 |
6 5 |
x1 |
|
23 |
||||
|
7 10 |
8 |
7 |
|
x |
|
32 |
|
|
|
|
|
|
2 |
|
|
|
|
6 8 10 |
9 |
|
|
|
|
|
|
|
|
|
33 |
|||||
5 7 |
9 10 |
|
xn |
|
31 |
Решение этой системы х1 = х2 = х3 = х4 = 1.
Если изменить правые части на 0,1 и принять их рав-
|
23,1 |
|
|
14,6 |
|
||
ными |
31,9 |
|
, то получим решение |
|
7,2 |
. |
|
X |
|||||||
|
32,9 |
|
|
|
2,5 |
|
|
|
31,1 |
|
|
|
|
3,1 |
|
68
Если принять величину 1-го коэффициента в 1-м уравнении равной 4,99 вместо 5, то получим решение
|
|
|
6 |
|
|
|
|
|
2,17 |
|
|
|
|
|
|
||
X |
|||||
|
0,28 |
|
|||
|
|
|
1,32 |
|
|
|
|
|
|
Существенно изменится при этом и обратная матрица. Следует отметить, что чем больше порядок системы, тем сильнее сказывается влияние небольших возмущений
коэффициентов системы на ее решение.
Обусловленность матрицы (системы) является качест-
венной характеристикой, хотя мы будем стараться оценить ее количественно. Существует несколько способов оценки обусловленности.
Например, обусловленность матрицы (системы) можно оценить с помощью величины, называемой мерой обу-
словленности (A):
A |
|
|
|
A |
|
|
|
|
|
|
|
A 1 |
|
|
|
, |
(3.26) |
|
|
|
|
|
|
|
|
|
|
||||||||
|
|
|
|
где A – норма матрицы А; A 1 – норма обратнойматрицы.
Число (A), часто обозначаемое cond A (от английского слова conditioned – «обусловленный»), служит также коэффициентом роста относительных погрешностей при неточном задании элементов матрицы А.
Чем больше (A), тем сильнее сказываются возмущения в исходных данных на решении системы линейных уравнений. Если число (A) велико, то система считается плохо обусловленной. Говорить о том, «что такое хорошо, а что такое плохо» в отрыве от контекста решаемой задачи, почти бессмысленно, так как здесь могут играть роль размерность задачи, точность, с которой должно быть найдено ее решение, точность представления чисел в ЭВМ и т.п.
69
Однако можно дать оценку снизу меры обусловленности.
Число обусловленности (A) не может быть меньше 1. Матрица, а соответственно, и система будет хорошо обу-
словленной, если (A) стремится к единице.
Пример 3.8. Оценим обусловленность матриц А и В:
1 |
0 |
3 |
4 |
|
|
1 |
20 0 |
0 |
||
A 0 |
1 |
5 |
6 |
, |
B |
0 |
1 |
20 |
0 |
|
|
5 |
4 |
0 |
2 |
|
|
0 |
0 |
1 |
20 |
|
3 |
6 2 |
0 |
|
|
0 |
0 |
0 |
1 |
Решение:
Обратные матрицы
|
|
|
0,00999 |
0,04245 |
0,14732 |
0,09114 |
|
A |
1 |
|
0,05618 |
0,01124 |
0,07865 |
0,11236 |
|
|
|
0,15356 |
0,09738 |
0,01498 |
0,02622 |
||
|
|
|
|
0,13733 |
0,08364 |
0,02559 |
0,00312 |
|
|
|
|
|
|
|
|
|
|
1 |
20 |
400 |
800 |
|
|
|
|
|
|
|
В 1 0 |
1 |
20 |
400 |
|
||||
|
|
|
|
|
|
|
|
|
|
0 |
0 |
1 |
20 |
|
|
|
|
|
|
|
|
|
|
|
0 |
0 |
0 |
1 |
|
Вычислим меры обусловленности. Для этого найдем |
||||||||||||||
нормы матрицы А: |
|
|
|
|
||||||||||
|
|
|
|
|
|
A |
|
|
|
max {8; 12; 11; 11} 12, |
||||
|
|
|
|
|
|
|
|
|||||||
|
A 1 |
|
|
|
max 0,291; |
0,258; |
0,292; 0,249 0,292. |
|||||||
|
|
|
Мера обусловленности (A) = 12 0,292 = 4,506 невелика и матрица А хорошо обусловлена.
70