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

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

                          (13)

и

                           (14)

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

, (15)

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

  ,   (16)

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

                               (17)

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

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

    (19)

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

  , где , (20)

так называемые конечные разности первого и второго порядков соответственно.

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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. Положить 

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

.

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

 

 

 

 

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

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 Сравнение методов

 

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

         

 

 

 

 

 

 

 

 

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

 

 

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

ПРИЛОЖЕНИЕ

Листинг программы

#include <math.h>

#include <stdio.h>

#include <conio.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()

{

  clrscr();

  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));

}

БЛОК СХЕМЫ

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

 

 

 

 

 

 

 

 

 

 

 

 

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