Учреждениеобразования
«Брестскийгосударственный университет имени А.С. Пушкина»
Кафедраинформатики и прикладной математики
Курсоваяработа
Методпростых итераций с попеременно чередующимся шагом
Брест2010
Содержание
Априорный выбор числаитераций в методе простых итераций с попеременно чередующимся шагом дляуравнений I рода
Постановка задачи
Сходимость при точнойправой части
Сходимость приприближенной правой части
Оценка погрешности
Априорный выбор числа итераций в методе простых итераций спопеременно чередующимся шагом для уравнений Iрода
Какизвестно, погрешность метода простых итераций с постоянным или переменным шагомзависит от суммы итерационных шагов и притом так, что для сокращения числаитераций желательно, чтобы итерационные шаги были как можно большими. Однако наэти шаги накладываются ограничения сверху. Возникает идея попытаться ослабитьэти ограничения. Это удаётся сделать, выбирая для шага два значения /> и /> попеременно, где /> уже не обязаноудовлетворять прежним требованиям.
Постановка задачи
Вгильбертовом пространстве /> решаетсяуравнение I рода /> сположительным ограниченным самосопряжённым оператором />, для которого нуль неявляется собственным значением. Используется итерационный метод
/>(4.1)
Предполагаясуществование единственного точного решения /> уравнения/> при точной правой части />, ищем его приближение /> при приближенной правойчасти />. В этом случае методпримет вид
/>(4.2)
Сходимость при точной правой части
/>
Считаем/>. Тогда, воспользовавшисьинтегральным представлением самосопряжённого оператора, получим
/>
Таккак
/>
Поэтому
/>
Если/>, то
/>
Если/>, то
/>
при/>,
/>
То
/>
Здесь/> ─ натуральныепоказатели, /> или />. Потребуем, чтобы здесь ивсюду ниже для />, удовлетворяющихусловию />, для /> было
/> (4.3)
длялюбого />, т.е. />. Правое неравенство даёт />. Так как />, то
/> (4.4)
Левоенеравенство даёт
/>.
Отсюда/>,
/> (4.5)
Из(4.4) и (4.5), двигаясь в обратном порядке, легко получить (4.3).Следовательно, условие (4.3) равносильно совокупности условий (4.4) и (4.5). Из(4.4) и (4.5) получаем следствие:
/> (4.6)
Докажемсходимость процесса (4.1) при точной правой части. Справедлива следующаятеорема.
Теорема:Итерационный процесс(4.1) при условиях />, /> и (4.3) сходится висходной норме гильбертова пространства.
Доказательство:
/>.
Приусловиях />, /> и (4.3) второй интегралсходится, так как
/>.
Здесь/>.
/>
таккак /> сильно стремится к нулюпри />. Таким образом, />. Теорема доказана.
Сходимость при приближенной правой части
Докажемсходимость процесса (4.2) при приближенной правой части уравнения />. Справедлива следующаятеорема.
Теорема: При условиях />, /> и (4.3) итерационныйпроцесс (4.2) сходится, если выбирать число итераций /> из условия />.
Доказательство: Рассмотрим
/>.
Оценим/>, где
/>
Найдёмна /> максимум подынтегральнойфункции
/>.
Таккак/>
Если/>, то />
Если/>, то
/>
при/>,
/>
поэтому/>. Отсюда получим />. Поскольку /> и />, то для сходимости метода(4.2) достаточно потребовать, чтобы />. Такимобразом, достаточно, чтобы />.Теорема доказана.
Оценка погрешности
Дляоценки скорости сходимости предположим истокопредставимость точного решения,т.е. />. Тогда
/>.
Дляупрощения будем считать число /> чётным,т.е. /> и найдём оценку для />. С этой целью оцениммодуль подынтегральной функции
/>.
/>. Первый сомножитель /> для/>. Второй сомножитель /> для малых /> близок к единице, т.е.тоже положителен. Поэтому /> покрайней мере для всех />, непревосходящих первой стационарной точки. Найдём стационарные точки функции />.
/>.
Первыедва сомножителя не равны нулю, в противном случае />.Следовательно, /> ─ полноеквадратное уравнение. Отсюда получим, что
/>
─стационарные точки функции />. Рассмотрим/>:
/>/>
где/>
/>.
Имеем
/>,
таккак первые два сомножителя при условии (4.3) положительны. Значит, /> ─ точка максимумафункции />. Оценим /> в точке />.
/>
Покажем,что
/>. (4.7)
Предположим,что (4.7) справедливо. Оно равносильно неравенству
/>,
которое,в свою очередь, равносильно такому
/> (4.8)
Возведениев квадрат обеих частей неравенства (4.8) даст эквивалентное неравенство, еслилевая часть неотрицательна. Установим, при каких /> этобудет.
/>
Очевидно,при />, />.
Будемсчитать /> и возведём обе частинеравенства (4.8) в квадрат. После приведения подобных членов получим
/> или
/>,
т.е./>.
При/> последнее неравенствосправедливо и, следовательно, в силу равносильности неравенств, справедливонеравенство (4.7). Отсюда
/>.
Оценимтеперь />. Покажем, что
/>, (4.9)
т.е./>, т.е.
/>
Преобразовавпоследнее неравенство, получим
/>
Послевозведения обеих частей неравенства в квадрат и приведения подобных членов,получим очевидное неравенство
/>.
Всилу равносильности неравенств справедливо неравенство (4.9), так что
/>.
Такимобразом, для /> справедлива оценка
/>.
Оценим/> в точке
/>.
Сначалапотребуем, чтобы />, т.е.
/>.
Усилимнеравенство
/>.
Отсюда/>. При />, причём, при />.Пусть />, тогда при условии
/> (4.10)
имеем/>, т.е. />. В противном случае />, и оно нас не интересует.Оценим при условии (4.10) функцию />.
Дляэтого сначала оценим />, так как в точке/> функция />. Найдем, при какихусловиях выполняется неравенство
/> (4.11)
Подставив/> в (4.11), получим
/>
чтопосле упрощения даёт
/>
Возведёмобе части неравенства в квадрат, получим
1случай:
/>
2случай:
/>
/>
/>
Следовательно:
/>
Очевидно,что при условии (4.5) это неравенство справедливо и, следовательно, справедливо(4.11). Итак, при условиях (4.5) и (4.10) справедлива оценка
/>.
Наконцах отрезка /> имеем />. Таким образом, получимследующие оценки для />:
1. в точке /> />;
2. в точке /> при условии (4.5) и (4.11)/>;
3. в точке /> />.
Найдёмусловия, при которых />, т.е. />. Это равносильно условию
/>. (4.12)
Такимобразом, если выбирать /> и /> из условия (4.12), то />.
Посколькугеометрическая прогрессия убывает быстрее, чем />,то /> для достаточно больших />. Поэтому для таких /> справедлива оценка />.
Таккак />, то при условиях />, (4.4), (4.5), (4.10) и(4.12) имеет место следующая оценка погрешности итерационного метода (4.2)
/>. (4.13)
Нетрудновидеть, что условие (4.12) сильнее условия (4.4). Для нахождения оптимальной по/> оценки погрешностипроизводную по /> от правой частивыражения (4.13) приравняем к нулю. Тогда оптимальная по /> оценка погрешности имеетвид
/> (4.14)
иполучается при
/>. (4.15)
Итак,доказана
Теорема:При условиях />, />, />, (4.10), (4.5), (4.12)оценка погрешности метода (4.2) имеет вид (4.13) при достаточно больших />. При этих же условияхоптимальная оценка имеет вид(4.14) и получается при /> из(4.15).
Такимобразом, оптимальная оценка метода (4.2) при неточности в правой частиуравнения оказывается такой же, как и оценка для метода простых итераций. Каквидно, метод (4.2) не дает преимущества в мажорантных оценках по сравнению сметодом простых итераций. Но он дает выигрыш в следующем. В методе простыхитераций с постоянным шагом (2) требуется условие />,в этом же методе с переменным шагом допускается более широкий диапазон /> для больших />. В методе (4.2) />. Следовательно, выбирая /> и /> соответствующим образом,можно считать /> в методе (4.2)примерно втрое меньшим, чем для метода простых итераций с постоянным шагом, ивдвое меньшим, чем для того метода с переменным шагом. Таким образом, используяметод (4.2), для достижения оптимальной точности достаточно сделать итерацийсоответственно в три раза или два раза меньше. Приведем несколько подходящихзначений />, удовлетворяющих требуемымусловиям:α 0,8 0,9 1,0 1,1 1,15 1,17 1,3 β 4,4 5,0 5,5 6,1 6,4 6,5 4,1
Наибольшуюсумму /> и, следовательно,наибольший выигрыш в объеме вычислений дают значения /> и />. Поскольку в выделенномслучае />, то условие (4.6)показывает, что достигнут практически максимальный возможный выигрыш.
Замечание: Оценки сходимости были получены дляслучая, когда />. В случае, когда/>, во всех оценках /> следует заменить на />.
Замечание: Считаем, что />. На самом деле всерезультаты легко переносятся на случай, когда />.
Литература
1. В.Ф. Савчук, О.В.Матысик «Регуляризация операторных уравнений в гильбертовом пространстве»,Брест, 2008, 195 стр.