Скалярная задача о неподвижной точке

ПРИДНЕСТРОВСКИЙ ГОСУДАРСТВЕННЫЙ  УНИВЕРСИТЕТ

 им. Т.Г. Шевченко

 

Рыбницкий филиал

 

кафедра физики, математики и информатики 

 

 

   

 

 

 

КУРСОВАЯ  РАБОТА

 

по дисциплине «Вычислительная  математика»

 

Тема: «Скалярная задача о неподвижной точке» 

 

 

 

 

 

 

 

Выполнил:

студент  II курса 220 гр,

специальности

«ПОВТ и АС»

Кириченко Д.А

 

 

Проверил

ст .преподаватель

Балан  Л. А.  

 

 

 

 

 

 

 

 

Рыбница

2011 г.

СОДЕРЖАНИЕ

ВВЕДЕНИЕ ......................................................................................................... 3

ГЛАВА I. ЗАДАЧА О НЕПОДВИЖНОЙ  ТОЧКЕ

1.1 Основные понятия ...………………………………………….……. 4

 1.2 Ускорение сходимости последовательных приближений ……... 10

          1.3 -процесс Эйткена ……..……………………………………….....11

 1.4 Алгоритм решения по методу Эйткена .......................................... 13

 1.5 Метод Вегстейна…………………………………………………... 15

 1.6 Алгоритм решения по методу Вегстейна....................................... 17   

ГЛАВА II. РАЗРАБОТКА ПРОГРАМНОГО  ПРОЕКТА

2.1 Реализация в С++…………………………………………………..18

 2.2 Сравнение методов ………………….…........................................20

ЗАКЛЮЧЕНИЕ………………………………………………………………..21

СПИСОК ЛИТЕРАТУРЫ…………………………………………………….22 

ПРИЛОЖЕНИЕ 

Листинг ………………………………………………………………………..23

Блок схемы…………………………………………………………………….24

 

ВВЕДЕНИЕ

        Многие инженерные задачи приводят к необходимости поиска решения уравнений, удовлетворяющих определенным условиям. Однако получить точное решение уравнения удается лишь в отдельных случаях, но даже при этом часто получают выражение, содержащее искомую функцию в неявном виде, что затрудняет ее использование.

Задача отыскания корня нелинейного  скалярного уравнения преобразуется  к эквивалентной задаче о нахождении неподвижной точки некоторого нелинейного  отображения в одномерном пространстве. К ней применяется метод простых итераций, изучаются условия и характер его сходимости. Далее  рассматриваются два способа ускорения сходимости МПИ. На логическом уравнении исследуется возможное поведение генерируемых МПИ последовательностей в случае нарушения одного из достаточных условий сходимости.

Курсовая работа состоит из двух разделов. В первом разделе приведены теоретические сведения, и применения метода Эйткена  и Вегстейна, оценка погрешности при его использовании, а также достоинства и недостатки данного метода. Во втором разделе приведена программная реализация данных методов в пакете MathCaD, Microsoft Excel, C++.

Целью курсовой работы является: разработка программного продукта для нахождения приближенного решения уравнения методом Эйткена  и методом Вегстейна.

Для достижения данной цели необходимо выполнить следующие  задачи:

1. Рассмотреть суть метода Эйткена.
2. Рассмотреть суть метода Вегстейна.
3. Назначение и область применения.
4. Провести сравнительный анализ данных методов.

 

 

ГЛАВА I. ЗАДАЧА О НЕПОДВИЖНОЙ ТОЧКЕ

 

1.1 Основные понятия

 

Рассмотрим нелинейное скалярное уравнение 

     (1)

где интерпретируется как отображение элементов из в . Решить данное уравнение ― это найти такой элемент заданного пространства, который при преобразовании посредством отображения остается неизменным:

     ( 2)

Этот элемент  называют неподвижной точкой отображения , а уравнение вида (1) ― задачей о неподвижной точке. Простейший процесс построения последовательности приближений к неподвижной точке отображения определяется формулой

                                (3)

что называют методом последовательных приближений или методом простых итераций (сокращенно МПИ). Сформулируем условия сходимости метода простых итераций (2) для задачи о неподвижной точке (1).

 

Теорема 1. Пусть функция определена и дифференцируема на отрезке . Тогда, если выполняются условия:

1) ,

2) ,

то уравнение (1) имеет и притом единственный на корень  ; к этому корню сходится определяемая методом простых итераций (3) последовательность , начинающаяся с любого .

 

Теорему 1 можно расшифровать так: нелинейная непрерывная математическая модель (1) некоего явления изучается путем построения и исследования соответствующей дискретной модели (3). Связь между этими моделями на отрезке устанавливается при выполнении двух следующих условий:

          (отображение в себя)             (3а)

и

       (сжатие)                                          (3б)

Эти условия согласно теореме 1, являются достаточными для существования и единственности на решения непрерывной задачи (1), причем оно может быть получено как предел последовательности (т.е. как решение дискретной задачи (3)), начинающейся с любой точки . Последнее можно расценить как устойчивость в данном смысле решения дискретной модели (3).

Возьмем за основу и будем рассматривать некоторую конкретную дискретную модель, а для ее исследования привлечем соответствующую непрерывную модель.

Попытаемся выяснить, к чему может привести нарушение условий сходимости метода простых итераций, т.е. условий (3), применительно к данной модели.

Введем в дискретное (разностное) уравнение (3) и непрерывное уравнение (1) вещественный параметр , т.е. будем изучать связь между моделями вида

,     ;                       (4)

и

,                              (5)

Представим себе следующую  весьма идеализированную картину. Пусть  на некоторой ограниченной территории, например, на острове, может прокормиться не более животных определенного вида, и пусть в начальный момент наблюдений за ними их количество было . Будем считать, что животные ежегодно приносят потомство, и скорость размножения характеризуется некоторым параметром . Тогда, если через обозначить численность животных в -й год после начала наблюдения, то можно предположить, что закон ежегодного изменения численности популяции грубо описывается моделью

,           (6)

В пользу принятия такой модели говорят  следующие рассуждения. Если значение начальной численности мало, то второй сомножитель в начале процесса почти постоянен, и все зависит от коэффициента роста : при малых , т.е. при низкой скорости размножения, численность животных будет снижаться и, в конце концов, популяция гибнет. Если же возрастает и приближается к максимально возможному значению , то за счет близости к нулю второго сомножителя численность популяции естественно начнет снижаться.

Чтобы облегчить исследование модели (6), упростим ее заменой переменных. Переписав (6) в виде

и положив  , , приходим к уравнению

                           (7)

где , а значения в соответствии со смыслом задачи должны принадлежать отрезку . Уравнение (7) называют логистическим.

На равенство (7) можно  смотреть как на метод простых  итераций (4), применяемый к задаче о неподвижной точке вида (5), т.е. к задаче о корнях уравнения

                               (8)

в области  .

Не используем далее в обозначениях функции ее явную зависимость от параметра , положим

и преобразуем эту  квадратичную функцию к виду

.

Из последнего следует, что  при и что отображает отрезок в . Значит, при функция осуществляет на отрезке отображение в себя, т.е. при этих элементы последовательности , получаемой с помощью равенства (7), при любом не выйдут за пределы , другими словами, определены при любом .

При нарушается соответствие между дискретной (4) и непрерывной (5) моделями. Например, при уже , то есть не принадлежит множеству, на котором определена функция .

Для производной данной функции  имеем:

и .

Следовательно, при  отображение является сжимающим на и имеет единственную неподвижную точку , а именно , которая является пределом последовательности при любом начальном значении (популяция гибнет по причине недостаточной скорости воспроизводства). Геометрическая иллюстрация этого случая показана на рис. 1.

Рис. 1. Сходимость МПИ (7) к корню логистического уравнения (8) при

Определение 1. Неподвижная точка отображения называется притягивающей на интервале , если для любой начальной точки будет выполнено:

 при  .

 

В частности, достаточным  условием, чтобы точка была притягивающей, является условие (если в точке производная меньше 1, то по непрерывности она будет такой и в некоторой окрестности этой точки, что позволяет говорить о сходимости последовательности, порождаемой процессом (7), по крайней мере, при значениях из окрестности ).

 

Определение 2. Если в некоторой точке имеет место неравенство , то эта точка называется отталкивающей.

 

Очевидно, что при  неподвижная точка является притягивающей, так как по теореме 1 для любой начальной точки выполняется условие при .

При нарушается одно из условий сходимости МПИ: не является функцией сжатия.

Очевидно, уравнение (8) по-прежнему сохраняет решение . Но при переходе через 1 это решение теряет устойчивость и появляется второе решение , которое следует считать устойчивым, поскольку теперь именно к нему будет сходиться любая последовательность, определяемая начатым с методом простых итераций (7) (см. рис. 2).

Рис. 2. Сходимость МПИ (7) к корню при

 

 

 

 

 

 

 

 

 

 

 

1.2 Ускорение сходимости последовательных приближений

МПИ (1) имеет лишь линейную сходимость, причём в случаях,  когда производная функции близка к единице, эта сходимость может быть весьма медленной.

 Один путь ускорения  сходимости МПИ- построение нестационарных процессов на основе МПИ. На стадии приведения уравнения к задаче о неподвижной точке, можно подметить последовательность уравнений

                        (9)

и соответствующей таким уравнениям формуле МПИ

     (10)

параметры   подбирать так, чтобы при этом учитывалась информация, получаемая на предыдущем шаге. Если, например, взять равную отношению единицы на  производную функции то уравнение (10) будет определять основной метод Ньютона, сходящийся квадратично.

Другой путь – это  алгоритмическое построение последовательностей, так или иначе «паразитирующих» на последовательности приближений МПИ (3), т.е. получаемых с помощью несложных арифметических манипуляций над несколькими членами последовательности ( ) и в результате имеющих более быструю сходимость. Для всех таких методов характерны многошаговость , экономичность ( поскольку более быстрая сходимость по сравнению с базовой последовательностью достигается без дополнительного вычисления значений функции), а также сложность исследования условий и скорости сходимости, отсюда – отсутствие эффективных априорных оценок погрешностей. Возможны ситуации, когда новый метод окажется сходящимся, в то время как базовый для него МПИ расходится. Рассмотрим два таких метода ускорения сходимости последовательности (3).

 

 

 

_{1.3 - процесс Эйткена}

 Пусть (Хк)- последовательность, получаемая по формуле (3), вычитая  (3) из (2), имеем    

                                      (11)

а уменьшив здесь индекс на единицу, получаем

                                     (12)