книги / Численные методы в теории упругости и пластичности
..pdfN |
т |
|
5(т) = Е |
с ' « П ( 1 - А Л« ) ^ ) - |
(1.46) |
4=0 |
п=1 |
|
Задавшись теперь некоторым числом итераций т (которое можно рассчитать в зависимости от требуемой точности 5), естественно определить последовательность итерационных параметров /?п, я = 0 , 1 , . . . , т , решением задачи
|
|
т |
пип |
шах |
(1.47) |
р |
А'<А<А" |
|
Э то приводит к полиному Чебышева, для которого известно, что он «наименее уклоняется от нуля», т.е. обращает в минимум выражение тахл'^А<Л" |-Рт(А)|1 где Рт (А) — полином порядка т . Тогда выражения для /?„ имеют вид
2
Однако на практике оказалось, что величины итерационных пара метров, подсчитанные по формуле (1.48), не приводят к успеху и даже часто наблюдается расходимость итерационного процесса. Обьяснение этому явлению, а также описание алгоритма, сог ласно которому последовательность /?„ выбирается специальным образом, даны в [125].
Используя результаты, полученные для решения системы (1.10), с помощью итерационной схемы (1.11) можно сформулировать те орему, которую в дальнейшем будем называть «основной тео ремой».
Основная теорема. Пусть задана система линейных уравне ний (1.10) и пусть А', А" — соответственно наименьшее и наиболь шее собственные значения матрицы А. Тогда процесс простой итерации (1.11) сходится со скоростью геометрической прогрес
сии со знаменателем |
|
д = тах(|1-/?А'|,|1-/?А"|), |
(1.49) |
если |
|
|
(1.50) |
Используя результаты упражнения 1.4, можно подсчитать чис ло итераций, необходимых для достижения заданной точности 6. Положим, например, N = 100. Пусть требуется уменьшить невязку в 105 раз. Тогда
А" |
1 |
8ЛГ2/2 , |
1 |
. |
т * » ' " |
в = |
4 Р ^ 1" |
« = 2 ' 3 3 ' 10 |
(1' |
На ЭВМ типа БЭСМ -4, делающей 105 операций в секунду, одна итерация (пересчет 104 значений в узлах сетки) занимает « 0 , 5 с. Поэтому согласно (1.61) весь расчет займет более трех часов машинного времени. Правда, в действительности необходимое число итераций для достижения указанной точности будет не сколько меньше.
Заметим, что в действительности мы не можем получить точ ного решения разностной задачи, например задачи (1.51), (1-52). В лучшем случае мы получим «машинное» решение, которое от личается от точного из-за округления чисел в ячейках памяти машины. Обозначим й„ и /„ соответствующие разностные функ
ции с учетом ошибки округления: |
|
3» = «»(! + *), /п=/»(1 + 6). |
(1.62) |
Подсчитаем ошибку аппроксимации разностного уравнения (1.51) с учетом ошибки округления 6\
Цп+1 - 2 й п + Ц п - 1 |
- Л - ( 0 - / ) п= °<‘ г>+ ° ( р ) + ОД- |
К2 |
(1.63) Следовательно, неразумно слишком уменьшать величину Л. Из (1.63) следует, что для данной задачи Н не должно быть меньше, чем Л = 0 (6 1>А). В современных ЭВМ величина 6 колеблется в пределах 10-8 10-12. Пусть д — разрядность ЭВМ , т — поря док аппроксимации оператора. Тогда величина шага Н должна удовлетворять соотношению
. Л = 0(1 0 “ ™+2). |
(1.64) |
Для качественной характеристики связи между погрешнос тями правой части решения вводятся понятия обусловленности системы и обусловленности матрицы системы. Обозначим 6 век тор ошибки правой части уравнения (1.4), а Л — вектор ошибки решения. Тогда
—* _ —»* |
—* |
(1.65) |
V = и |
—и, |
|
И1 = 1|Л-11НЙ1- |
( 1 .66) |
|
Мерой обусловленности системы назовем число
ц = т а х |
М тахМ |
(1.67) |
|
И 1 * \ Щ \ |
|
В силу определения числа ц верна оценка для погрешности ре шения
М < Л ! |
(1.68) |
И«*И ^ ^||/ц
Устойчивость системы гарантирована конечностью числа ц, при чем чем меньше это число, тем точнее решение.
Вычислим теперь меру обусловленности /I. Из (1.68) видно, что наибольшее значение ||?||будет принимать в случае равенства, т.е. при
Н Л - ^ т а х О |
(1.69) |
|
* |
№11 |
|
Тогда из (1.67) иммем |
|
|
ц = |
|
(1-70) |
Однако величину ||й*|| мы не знаем. |
Поэтому |
вводят величину |
и — меру обусловленности матрицы А\ |
|
|
и = шах и. |
(1.71) |
|
1|7||
Неравенство (1.68) может быть заменено неравенством
|
V/ |
(ха |
но |
|
|
11711 Ни1 |
шах |
= ||Л||. |
||3*|| |
||и | |
Тогда для I/, принимая во внимание (1.71), получаем
* = \а\а-%
(1.72)
(1.73)
(1.74)
Если мы положим, например, ||3||= (3 ,З)1/2, где (3,8) скалярное произведение в евклидовом пространстве, то
(1.75)
С другой стороны
(1.76)
Поэтому
А"
А '' |
(1.77) |
|
|
Из соотношения (1.61) видно, что |
|
|
2 |
|
(1.78) |
|
V |
Следовательно, чем больше мера обусловленности матрицы систе мы, тем больше итераций потребуется для достижения заданной точности.
§ 2. ИТЕРАЦИОННЫЕ М ЕТОДЫ СО СЛОЖНЫМИ ОПЕРАТОРАМИ ОБРАЩЕНИЯ
Рассмотрим систему линейных уравнений
Ьи = /. |
(2.1) |
В предыдущем параграфе были рассмотрены итерационные про цессы для решения (2.1), в которых для получения т + 1 .при ближения нужно было знать только то-е приближение. Можно рассмотреть более общий случай. Так как в конечномерном пространстве всякий оператор, переводящий вектор в вектор, определяетоГ матрицей, то мы будем называть матрицы типа Ь также операторами. Рассмотрим операторы Ат, А ^ \
•••> 4т^> Лт , где нижний индекс означает номер итерации, а верхний — номер оператора. Тогда многослойная итерационная схема может быть записана так [23]:
Для того, чтобы соотношение (2.2) удовлетворялось для решения 3* уравнения (2.1), необходимо, чтобы существовала связь между операторами:
Ат = 4™т ) + 4 % - 1) + ■■■+ 4 |
$ + -вть . |
(2.3) |
Упражнение 2.1. Показать, что для двуслойной схемы из (2.2) имеем
Лт и(т+1) = Лт «(т ) - В т[Ь и ^ - /]. ■ |
(2.4) |
Рассмотрим частный случай итерационной схемы (2.4), когда оператор В т имеет вид
В т = АпЕ, |
(2.5) |
где (Зт — итерационные параметры. Из (2.4) видно, что для пере хода от т-го приближения к т + 1-му нужно обратить опрератор Ат, который называется оператором обращения. Обозначим Л” 1 оператор, обратный к Ат. Введем обозначение
Ст = А -'Ь |
(2.6) |
и назовем оператор |
|
Зт = Е - 0 тСт |
(2.7) |
оператором перехода. Тогда итерационная схема (2.4) |
приоб |
ретает вид |
|
5(т+1) = 5(т) - / и с т «<"*) - А -1/] = |
+ ВпА-1}. |
(2.8) |
Вводя вектор ошибки по формуле (1.12), получим из (2.8) |
|
|
?(т+1) = 5 т 3<т >. |
|
(2.9) |
Оператор Т т, обладающий свойством |
|
|
*(т) = Г т ”(0), |
|
(2.10) |
называется разрешающим оператором. Из (2.9) видно, что |
|
|
Тт = ?т-1--&0- |
( 2 - 1 1 ) |
Упражнение 2.2. Показать, что для случая, когда оператор обращения и итерационные параметры не зависят от шага итера ции, оператор перехода и разрешающий оператор имеют вид
5 т = 5 = Е - 0 С , |
С = А~1Ь, |
(2.12) |
Тт = (§ )" - |
■ |
(2.13) |
Будем обозначать скалярное произведение двух векторов 3, 3 в евклидовом пространстве (3,3), а длину вектора и
Н«Н = (Й>«)1/2. |
(2-14) |
Все операторы, с которыми мы будем иметь дело, считаем поло жительно определенными и самосопряженными. Условие
(Ли, и) > /<||3||2 |
(2.15) |
сокращенно запишем в виде |
|
А > цЕ . |
(2.16) |
Будем говорить, что линейный оператор Ь эквивалентен по спек тру оператору А, и записывать Ь ~ А [23], если существуют такие
числа но и (Л1> 0 < Но ^ |
что |
|
|
НоА ^ Ь ^ Н^А. |
(2-17) |
Тогда основную теорему, доказанную в предыдущем параграфе, можно сформулировать так. Пусть задан итерационный процесс
Ли(т+1>= Ли<т >- 0[Ьи^т) - /] |
(2.18) |
||
для решения уравнения (2.1). |
И пусть известно, что |
|
|
А'# < С < А"Я, |
С ~ А ~ 1Ь. |
(2.19) |
|
Так как норма оператора определяется выражением |
|
||
||5|| = |
зир |
|(53,3)|, |
(2.20) |
|
Ц2||=1 |
|
|
то, учитывал (2.12),
(53, и) = ||3||2 - 0(Сй, и). |
(2.21) |
1-/?А" ^ (53,3) < 1-/?А'. |
(2.22) |
Следовательно, |
|
||5||= д = шах(|1-/?А'|)|1-/?А"|), |
(2.23) |
откуда и следуют результаты основной теоремы.
Оператор обращения А выбирают обычно так, чтобы он легко обращался и число итераций для достижения заданной точности было как можно меньше. При построении оператора обращения А стараются выбрать его в каком-то смысле близким к оператору Ь системы (2.1).
Разберем частный случай. Пусть, например, оператор Ь ~ А, т.е. существуют две положительные константы ц' и р", такие, что
ц 'А ^ Ь ^ ц"А. |
(2.24) |
Пусть, кроме того, оператор Ь может быть представлен в виде
суммы одномерных операторов Е , и ^ |
[107]: |
|
— Е , + Л2. |
|
(2.25) |
Предположим далее, что операторы |
и Д2 обладают следую |
|
щими свойствами: |
|
|
г'а Е ^ К а ^г'^Е, 0 < г ^ г " , а =1,2, |
(2.26) |
|
Л1Л2 — |
|
(2.27) |
Тогда оператор обращения А можно выбрать в факторизован ном виде:
А = А,А 2, |
Аа = Е + раЯ а , ог = 1,2, |
(2.28) |
где /?1 , /?2 — некоторые итерационные параметры. |
|
|
Упражнение 2.3. |
Показать, что для итерационной |
схемы |
(2.18), где оператор обращения имеет вид (2.28), оператор перехо да 5 = Е —&С, С = А~ГЬ, можно представить следующим образом:
3 = 5,52, 5, =
§2 = (Е + /?гЛ2) 1(Е —/3,Е2), |
(2.29) |
|
|
если |
(2.30) |
/? = /?! + /?2- ■ |
5(т+1) _ |
(2.31) |
|
Поэтому можно применить метод переменных направлений:
8 2^ т) = «<"•+*),
|
5 1^ т + 2> - |
г("»+1) |
|
(2.32) |
|
|
|
||
Упражнение 2.4. |
Показать, что уравнения (2<32) могут быть |
|||
записаны в виде |
|
|
|
|
, |
о(т +а) - 5(”*) |
, . |
|
|
4 2-------- р -------- + я 2* (т) = о, |
(2.33) |
|||
о(т +!) _ 5("»+^) |
|
|
||
+ § 1г<т +*) = о. |
|
|||
4г |
|
|
||
Упражнение 2.5. |
Показать, что из (2.26) и (2.28) следует |
|||
^ |
4 . |
+ |
« = 1 ,2 , |
(2.34) |
или |
|
|
|
|
,/ 4 а ^ Яа ^ < А п , а |
=1 ,2 . |
(2.35) |
||
1 + /?а г; |
1 + Л < |
|
|
|
Согласно основной теореме для каждой из систем (2.33) получим наилучший выбор итерационных параметров:
—01 + 02, « = 1,2, |
(2.36) |
1+А.7Гг; т+ 1+^лГ»
т.е. систему двух уравнений относительно 0 \ и 02. Упражнение 2.6. Показать, что для случая
0 1 — 0 2 = |
0 0 |
(2.37) |
система (2.36) имеет решение |
|
|
0о — 1 |
1 |
(2.38) |
Из (2.38) следует, что случай (2.37) возможен только при выпол нении условия
Г1Г1 = Г2Г2- |
(2.39) |
Более того, если применить к схеме (2.18) основную теорему, то считая ц' и у," в (2.24) известными, получим, что условие (2.37 будет выполняться, если
Ы + и")2 = г! г? = г'2т'{. |
(2.40; |
Бели не делать предположения (2.37), то систему (2.36) мажне решить следующим образом [107]. Совершим преобразование
г[ = г7! + а, г" = г" + а, |
г'2 = г'2 - |
а, г2 = г'2 - а |
(2.41) |
|
с тем, чтобы выполнялось, (2.39) для т'а |
и г", |
т.е. |
|
|
(г[ + а)(г“ + а) = (Г2 - а)(г? - |
а). |
(2.42) |
||
Отсюда |
ЛтЧ - г[г'{ |
|
|
|
_ |
|
|
(2.43) |
|
а = |
|
|
|
|
Г1 + Г1 + »2 + г2 ‘
Тогда, считая, что преобразование (2.41) выполнено так, чтобы
Ь = Ну + К2 = |
+ Дз, получим |
|
|
|
Д1 — |
4е с Е , ^ |
— ^2 — оЕ . |
(2.44) |
|
Поэтому из (2.29) |
следует |
|
|
|
|
|
5 = 5 = 5 15 2, |
|
|
?1 = [Б + А(Д1 + °Б)] |
*[Б —/®2(1?1 + О-?)]) |
(2.45) |
||
|3 = [^ ■+ Д(Да - а Б )]-1^ - А (& - аБ)]. |
|
|||
Отсюда |
а - |
й |
- |
|
|
(2.46) |
|||
|
Л |
1 + а/?0 ’ |
1 — а/?0 ’ |
|
где Д, определяется по формуле |
|
|
||
|
|
1 |
1 |
(2.47) |
|
|
|
|
|
а величина а — по формуле (2.43).
Следовательно, имеет место сходимость итерационного про цесса (2.18) со скоростью геометрической прогрессии со знаме
нателем ф, причем |
|
Я = ||$1|= Я & 2 , дхнН^Н, д 2 = ||52||. |
(2.48) |