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

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Министерство образования и науки Российской Федерации

Федеральное государственное бюджетное образовательное учреждение

«Ижевский государственный технический университет имени М.Т. Калашникова»

Кафедра АСОИУ

Пояснительная записка к курсовой работе

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

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

Выполнила:

Студентка группы Б3-782-2зт

Калимуллина А.Ф.

Проверил:

Ст. преподаватель кафедры АСОИУ

Е.Н. Исенбаева

Ижевск 2014 год

Содержание

скалярный уравнение нелинейный

Введение

1. Задача о неподвижной точке

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

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

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

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

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

1.6 Алгоритм Вегстейна

2. Разработка программного проекта

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

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

Заключение

Список литературы

Введение

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

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

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

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

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

Рассмотреть суть метода Эйткена.

Рассмотреть суть метода Вегстейна.

Назначение и область применения.

Провести сравнительный анализ данных методов.

1. Задача о неподвижной точке

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)

К правым частям этих равенств применим формулу Лагранжа, согласно которой найдутся точки и такие, что

(13)

(14)

Таким образом, имеют место следующие связи между ошибками соседних приближений:

, (15)

Предположим, что в этой окрестности корня , в которой находятся точки и , производная меняется не очень быстро. Это допущение позволяет считать что (где - некоторое число), и значит,

, (16)

Беря отношение этих приближённых равенств, избавляемся от :

 (17)

и разрешаем полученное приближённое уравнение относительно неизвестной величины

: (18)

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

(19)

Более коротко можно записать так:

, (20)

так называемые конечные разности первого и второго порядков соответственно. Организация вычислений на основе этого преобразования может быть различной. Наиболее целесообразным считается применение - ускорения через два шага МПИ на третий [1].

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

Шаг 0.

Ввод (начального приближения), (исходной функции),q (оценки модуля производной), (допустимой абсолютной погрешности)

Шаг 1.

Вычисление значений:

Шаг 2.

Шаг 3.

Вычисление контрольного значения

Шаг 4.

Проверка на точность: если , то если положить , вычислить и вернуться к шагу 2.

Шаг 5.

Положить

Шаг ускорения по методу Эйткена на базе последовательности , получаемой МПИ (3),имеет простую геометрическую интерпретацию.

Надёжность метода выше в случае, когда , применение более актуально, если , и ускорение тем эффективней, чем меньше в окрестности корня .

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

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

Отсюда получаем приближённые равенства

,

следствием которых является равенство (о), приводящее к формуле (к).

Применение - преобразования Эйткена к последовательностям, сходящимся квадратично, эффекта ускорения не даёт.

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

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

Пусть уже найдены: - элемент строящейся последовательности, и - точка, соответствующая одному шагу МПИ, применённого в точке . Независимо от того, сходится начатый с МПИ или расходится, отрезок АВ, параллельный оси Ох и имеющий концами точки и , можно разделить точкой С так, чтобы она принадлежала вертикальной прямой .

При любых комбинациях направлений возрастания и выпуклости графика функции в окрестности неподвижной точки длины отрезков ВС и РС равны. Различаются два случая: когда и когда .

По формуле Лагранжа получим:

(21)

(22)

Можно утверждать, что существует точка такая что

 (23)

Разрешая уравнение относительно , получим

(у) (24)

Если бы значение было известно, то тем самым задача о неподвижной точке была бы решена точно. Заменим это неизвестное значение аппроксимирующим его разностным отношением:

(25)

Подставляя приближённое значение в (у) вместо корня получаем приближение к нему

- ф-ла Вегстейна (26)

Эта итерационная формула, где k=1,2,3,…, совместно с формулой

(k=0,1,2,…)

и начальными значениями полностью определяет метод Вегстейна для задачи о неподвижной точке.

Значение , получаемое по формуле Вегстейна при заданных начальных значениях и , совпадает со значением , вычисляемым -процессом Эйткена. В случаях, когда , можно заканчивать процесс вычислений. Выполняется, при условии (27)

1.6 Алгоритм Вегстейна

Шаг 0.

Ввод (начальное приближение), (исходную функцию),q (оценку модуля производной), (допустимую абсолютную погрешность)

Шаг 1.

Вычислить , положить

Шаг 2. Вычислить

Шаг 3. Проверить на точность: если , то вычислить ; переприсвоить значения и вернуться к шагу 2.

Шаг 4. Положить

Проверку на точность в таком алгоритме можно взять другую ( что просто необходимо, если метод Вегстейна применяется в случаях, когда .

Если нет угрозы большой потери точности из-за вычитания близких чисел, о заканчивать работу алгоритма Вегстейна лучше выводом значения . Для вычисления значения в этом алгоритме применена равносильная формула , имеющая несколько отличную от формулы Вегстейна структуру[2].

2. Разработка программного проекта

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

Метод Эйткена.

#include <math.h>

#include <stdio.h>

double x[11],f[11];

double Eitken(double X,int n)

{

double Y[51][51];

for(int j=0; j<=n; j++){

Y[j][j]=f[j];

for(int i=j-1; i>=0; i--)

Y[i][j]=1/(x[j]-x[i])*((X-x[i])*Y[i+1][j]-(X-x[j])*Y[i][j-1]);

}

return Y[0][n];

}

void main()

{

double X = 2.4800;

x[0] = 0.8496; f[0] = -0.3721;

x[1] = 0.9648; f[1] = -0.0742;

x[2] = 1.4072; f[2] = 0.3845;

x[3] = 1.8048; f[3] = 0.1878;

x[4] = 2.1920; f[4] = -0.1849;

x[5] = 2.4232; f[5] = -0.3474;

x[6] = 3.6152; f[6] = 2.5986;

x[7] = 3.6800; f[7] = 3.0616;

x[8] = 4.5024; f[8] = 13.1676;

x[9] = 5.1672; f[9] = 28.6035;

x[10] = 6.0424; f[10] = 62.0144;

printf("Eitken: f(%f) = %f \n",X,Eitken(X,10));

}

В функции double Eitken реализована формула по которой производится вычисление значений.

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

Как показываю многочисленные опыты с уравнениями вида , особый интерес среди которых вызывают случаи, когда простые итерации дают расходящиеся последовательности , метод Вегстейна имеет определённые преимущества перед методом Эйткена по количеству обращений к вычислению значений для получения корня с заданной точностью. На рисунке 3 и на рисунке 4 изображены блок схемы метода Эйткена и Вегстейна соответственно.



Рисунок 3. Блок схема метода Эйткена



Рисунок 4. Блок схема метода Вегстейна

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

Заключение

Миллионы людей занимаются математическими расчетами, иногда в силу влечения к таинствам математики и ее внутренней красоте, а чаще в силу профессиональной или иной необходимости, не говоря уже об учебе. Ни одна серьезная разработка в любой отрасли науки и производства не обходится без трудоемких математических расчетов. Система Mathcad и Microsoft Excel пользуется огромной популярностью во всем мире, позволяя готовить вполне профессиональные документы, имеющие вид статей и книг по математике.

В данном курсовом проекте была проделана работа по написанию программного продукта на языке C. Был изучен теоретический материал, необходимый для создания программы. Были закреплены знания и умения:

Данная курсовая работа позволила мне более близко познакомиться с пакетом прикладных программ MathCAD и Microsoft Excel. Мной было рассмотрено несколько способов решения дифференциальных уравнений.

Всё это позволило в полном объеме усвоить лекционный материал и понять перспективы использования вычислительной техники при решении различных задач практического характера.

Приведенные в работе результаты тестирования программы доказывают эффективность ее работы.

Список литературы

1. Вержбицкий В.М. Численные методы (линейная алгебра и нелинейные уравнения). 2-е изд. -- М.: Оникс 21 век, 2005.

2. Вержбицкий В.М. Основы численных методов. 3-е изд. -- М.: Высшая школа, 2009.

Размещено на Allbest.ru

...