Н.С. Бахвалов, Н.П. Жидков, Г.М. Кобельков - Численные методы (djvu) (1160088), страница 51
Текст из файла (страница 51)
(6) Поделив второе из соотношений (3) на 1 — (Л" ), получим Л вЂ” Л(а) , +о((лт~ ) ==+Ю. л'(,л ~0()лз() Из (5), (6) следует те" (Л~ — Л~~ )! = 0()лз!"); поэтому х" — хв ' 1 — (Л',"') ' — = ж'* Ц- О(~Лэ)"). Отсюда и згз (2) получаем Х'* — Х= в+О()лт~в), )улв справедливости приближенного равевсгва (Т) х — Хмч" где ти = (х" — х" з)/(1 — (Л1 1) ). Замегилг, что согласно (3), (6) ))тв)( = )сг((лз!в -~- ООЛэ)с).
Из этих равенств вытекает, что ии удовлетворяет критерию (1), и поэтому его можно привять за практическую погрешность приближения хсц В случае с| = - = гэ = О, сры ~ О проведенные рассуждения огланутся в силе, если (Льег) > (Льет~. Во всех соотношениях слелует заменить лигпь Лз сз ег при г = 1, 2 на Лсьп смп еьм Описанный способ получения оценки приближенного решения называется сз-процсссоас Если положить у = х" — и", то у" — Х =- 0((Лз)"), и поэтому у", вообще говоря, является лучшим начальным угловием для последующих итераций по сравнению с х".
Производя время от времени такие уточнения, иногда удается существенно уменьшить общее число итераций. Глава б. Численные мвщцы аип«бры 274 необходимо, чтобы в правой чанги равепстнв х' — Х=~ сЛ е, одно нз слагаемых преобладало вад оста.льнымв. Если вто твк, то вгкторь« х" — хи ', х" ' — хе г првблвзитгльно пропорцнопальнм и ))х"-' — х" т))))х" ' — х")) Таким образом, усювиг 1«~ 1 явлланм шюбходвмым длн того, чтобы проводившиеся ранее гюстрогпия были справедливы. Поэтеьгу его ьюлгво првнять за усвовне пракгическов прял«енимостп 17). Пшгрцмгр, возможна ссюлугогцая сзньщ мщода просней вшрвцнв с црвмгн«.
вием бюпр«гцосга ус«юренпя сходи«гости. Задшоэ«м некоторым О' н щи делах 1 > «1' > О и лгвлым д > О. Есаи по ходу итераций оказалогь, чтт«д > 1 — «1, ш шгшнсляется т«и вектор у" пршо«маек я за вач мгьни щ нближшпю дли п«хлш ующнх втераций. И и рацновный процесс прекращается, если д > 1 — О' и ))ни)! < г, где г требуемая точность. Если ц очень мала, то условно д«> ! — «1 будет выполняться т«щько пшме бшпшопг числа итераций, гскогннпо «ходимооги ие будет имггь мес«а. Пря блшыпом О ахггношевпя, пололавшыг в основу наших востро«ний, выполнвюпн грубо, поэтому нг исключено, «то применение бг-привесов гхслкмости зшпщлит итерационный процесс.
Картина итераций также ослогкняещи паличигм погрепщосги округяевий, так что описанная выше схгь«а требует праити'юской отработки па Гки«ьп~оы чп«лг примеров с целью выбора оптимальных «12 «1 н указашщ шок ней грюшцы зна «ел ий г, прн коз орь«х влгоритл«применим. Ясли однородный вп"радновный пропгст. подвергаегсв перестройке 1в вашем случае при переходе ш х«к у"), тв ив«яда гнпвпио проверигь, ио ведет .пн шн перестройке к ухудшению. В квчгстне критерия цолесообразностп перестройки «южно кщть некоторое соотношение, связьгвающее нормы незя«ок Лля х'", у, например неравенство вода ))1Š— В)у" — с)) < Ч)ИŠ— В)хе — с)).
Замечание О г!(юбходимосгн ухюання гщгке««й грэг«и «на'в«кпй г вгшынэегщ« сл«шуюпп«м обстовтельсгвоь«. Прть для опргзгеленносги Л«> О. Оггке орв эышслевин х" цо заданному х" ' лотре«пвогти округлгпвл ьюгут возлгутпть результат па величину дхе г нормой порядна р. Следствие«« этого м«пкет явиться возмущение Бт", имеющее норму порялка (1 — Лг) гр. Стсюла стелу~ г, что в случае г < 11 — Лг) 'р «ггерапнониый процесс может никогда не закончиться.
Проведенные востр«миня показмвают, по при реализации метода возникаег много такпк моментов, разбор коюрых требует серьезной ьгатгмнтнческой под. готовки и проведения большой терни числеинык экспериментов. П«г«тому, несмотря на «про<титу мег«ша простой« мгерации, булет вполне опрааданвым создэние стандаргпой программы этого метода. 276 ! б. Оптимизацн» скорости схадимасти шери!ванных процессов О 6. Оптимизация скорости сходимости итерационных процессов Рассмотрим простейший ишрациавный способ решения системы уравнений Ах =Ь: хп+' = х" — о(Ах" — Ь).
Мы видели, чта скорость схадимасти такога итерационного процесса существенно зависит от максимальнага ыодуля гюбственных значений матрицы В =  — аА. Егли Лы..., ˄— собственные звачения матрицы А, то шах)Лг(В)[ = шах[1 — оЛ,[. Из рис.
6.6.1 видно, что прн действительных собственных вне~синях различных зевков этот макг,нмум больше ! и итерэциогпгый процесс расходится. Обратимсн к часта встречающемуся случаю, когда все Л, > О. Значения Л! быпшот известны крайне редко, однако довольно типичен скучай, когда известна оценка для этих чисел вида О < р. < Лг < М < сю при всех ь Скорогзь сходимаств итерационного процесса можно характеризовать величиной Р(а) = шах [1 — оЛ[. ацл<м Рассмотрим задачу минимизации р(о) за счет выбора а.
Рнс. 6.6.1 Для нахождения ш!пр(о) удобна обратиться к геометрической картине (рнс. 6.6.2). Ясно, что р(о) > 1 прн о ч О. При О < н < М ! функция 1 — сгЛ нестрнцазельна и монотонно убывает на отрезке [Р, М[, поэтому Р(о) = 1 — од. При М ! < о пеличипа 1 — оМ отрицательна и модуль ее Растет с Раасом о. ПРи некотоРам о = оа насгУпит момент, кагДа 1 — гад = — (1 — нам), Н тогда р(оэ) = [1 — аар[. Если а ( оа, то р(о) = 1 — ад > 1 — аэр = Р(ое)! если оа < а, то Аа) > [1 — сгМ[ = Ма — 1 > Моа — 1 = Р(ое). Глава б.
Чясзеяяые месцзы алгебры Таким образом, значение а =- аа является искомым. Решая уравнение (1) атносижпьссо ао, получим ао = 2/(М+ р). Отсюда р(ао) = (М вЂ” р)/(М+ р). Зццача 1. Доказать сходимость итерационного процесса при а = ~(А1 — ' На примере систем с лсатрнцей А > О (здесь и далее неравенство А > О означает, чзю Л вЂ” симыегричная положительно определенная ыатрица) расаяотрим более формалнзоваспсые постановки праблеы оптимизации скорости сходимасти итерационных процессов.
Если число ненулевых элементов матрицы много больше се размерности, та операция умножения матрицы на вектор более трудоемка, чем умножение числа на вектор илв сложение всктаухсв. Поэтому при оценке трудоемкости итерационвых щюцессов и оптимизации этих процессов далее за меру трудоемкости мы неявно принимаем число умножений матрицы А на вектор.
Всякая система Ах =- Ь с бес Л и О, вообще говоря, ыожет быть приведена (как говорят, ссыьяешщсзавосса) умножением обеих часней уравнения па матрицу Ас к системе с симметричной положительно определенной матрицей. В самом деле, сисчеьса АГАХ =- АсЬ эквивалентна исхалной, матрица АтА симметричная, так как АзА = (АсА)с, и псжожительно определона, зак как (АГАХ, х) = ()Ах()т > О прн х ф. О. По возмсэкнастн сгаракизся избегать симмегризацви, поскольку, как мы увиден далее, ана часто приводит к ухудшению стадимости гггерационных процессов. Рассмотрим несколько более абсций итерационный метод, чем метод щюстой итерации.
А именно, в методе простой итерации ха+с = хь — т(Ахс — Ь) будем считать, что итерационный параметр т может изменятьмс от шага к шасу. Тогда метод примет вид х"+' = х" †.„, (Л ' — Ь), й = О, 1, . (2) где х — некоторое начюп,нос приближение. Зададимся некоторыьс целым и > О и щюизведем и итерацьб по фоР- муле (2). Согласно (2) пагрепнюсть г" = хг — Х удонлетворяег соотношению г = г — д,.смАг = (Š— тььсА)г . ь+1 ь с ь Тогда через и шагов итерационного метаца (2) погрешность г" будет выражаться через погрешность начальнага приближения г следуюпсим Образом: г = (Š— таА)г" ' = ". = (Š— г„А)...
(Š— тсА)го, (4) где г" = хо — Х вЂ” -погрешность начального приближения. 277 $ б. Оптимизация скорости схадимасти ((г<' (АН = ах (1Г (Л>)(, (б) где Л.— >х>бствепные значения А. Предположим, что Л> б (р, М), р > О.
Поскольку >х>бственные значения в (б) неизвестны, а извеспан талька интервал, которому гюи принадлежат, то задачу нахождения нормы операхх>ра Оп(А) заменим задачей оценки нормы шаго оператора при угл»вии, что мы знаем шр>нок, которому припад>п>жвт спектр А, т.е. ((1)„(А)(( = швх (О„(Л)(. Заметим, чтю мно>ючлеп Ов(Л) пиит вид а<л<м Оп(Л) = 1+ ° ° . Введем класс К„мпо>ючленав степени не выше и, равных единице в точке О Таким образом, мы можеи переформулировать исххшную залачу оптимизации слепу>шцим образом. На клмхп Кв требуется найти много шее г)~,(Л) такай, чтю Я,",(А) = агб ппп ((1я„(А)(( = агй пш»пах Я„(Л)(; (7) О„ег\ О ек„а<хял> здесь'агй, как обычно, означает аргумент, т.а.
мы ищем мцогочлен 1)„б Кп, дпа ватой»гг> имеет место Равенство шш ((Я„(А)(( = ((1<эв~(А)((. Ю егг„ На самом деле, вводя класс К, мы распшрили класс многочленов, пгижшьку в исходной постановке задачи прелполшалогь, что па (р, М) искомый многочлен должен иметь п корней. Тем пе менее, как мы увидим далее, данное расширение класса ве изменяет результат решения оцтимичациовной задачи. Лемма. Справедливо равенство Оа,(Л) = У;,>Т„( +" ), М вЂ” д (В) В)е Тп — инавочлеп Чебышева сглепеип и, а уп = То (и+--Л~).
Дакавашельсшва. Предположим, что утверждение леммы неверна, т. е. Что сУЩествУет многачлен 1У Е К„с ноРмой, меньшей, чги У 1Г>ш "1ак Обозначим хг„(А) = (ТУ вЂ” г А)... (Š— т>А). Таким образом, оператор (матрица) 1<о(А) связывает погрешности приближении на нулевом и и-м ахатах итерационного процесса.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
