Нахождение корней полиномов Эрмита

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

МАТЕМАТИКО-МЕХАНИЧЕСКИЙ ФАКУЛЬТЕТ

 

 

 

 

 

 

 

 

 

 

 

 

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

на тему:

«Нахождение корней полиномов Эрмита»

 

Преподаватель:

Самокиш Б.А.

 

Студента 261 группы

Лебедковой Татьяны

 

 

 

 

 

 

 

 

 

 

2008 г.

Постановка  задачи:

 

Используя рекуррентную формулу и какой-нибудь способ решения  уравнений, найти корни полиномов  Эрмита.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Решение поставленной задачи

Чтобы решить поставленную задачу, нужно сначала узнать, что же представляют собой полиномы Эрмита. А корни полиномов я решила найти методом Ньютона.

Все это я опишу  ниже.

 

 

1.Что такое полиномы Эрмита

 

Многочлен Эрмита по определению:

фор.1

 

H_n (x) – полином Эрмита

n – степень полинома

Многочлен 0 и 1 степени удобней  вычислить  по формуле 1.

Они имеют вид:

 

 

 

 

 

Также для вычисления полиномов Эрмита существует рекуррентная формула, имеющая следующий вид:

 

 

 

 фор.2

 

 

 

 

 

 

 

Это рекуррентное соотношение  можно вывести из формулы 1

 

Но, чтобы вычислить по ней полиномы, нужно знать полиномы 0 и 1 степени.

Поэтому эти 2 полинома я вычислила по формуле 1.

А полиномы степени от 2 и больше легко вычисляются по формуле 2.

Например, полиномы 2,3 порядка выглядят так:

 

 

 

Чтобы найти корни полиномов  Эрмита методом Ньютона, который описан ниже, требуется производная от функции, эквивалентной полиному Эрмита.

Из формулы 2 получается следующая  производная:

 

Однако существует более короткая формула для нахождения производных:

  фор.3

Эта формула получается следующим образом:

 

 

Производные многочленов  Эрмита первых порядков имеют следующий  вид:

 

 

2. Метод Ньютона  для решения уравнения

Обоснование

Чтобы численно решить уравнение   методом простой итерации, его необходимо привести к следующей форме: , где — сжимающее отображение.

Для наилучшей сходимости метода в  точке очередного приближения должно выполняться условие . Решение данного уравнения ищут в виде , тогда:

В предположении, что  точка приближения «достаточно  близка» к корню  , и что заданная функция непрерывна , окончательная формула для такова:

С учётом этого функция  определяется выражением:

Эта функция в окрестности  корня осуществляет сжимающее отображение, и алгоритм нахождения численного решения уравнения сводится к итерационной процедуре вычисления:

По теореме Банаха последовательность приближений стремится  к корню уравнения 

Иллюстрация метода Ньютона 

 

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

Алгоритм

1. Задается начальное приближение x₀(n = 0) такое, что
2. Вычисляется следующее приближение:
• Если (то есть погрешность в нужных пределах), то x_{n + 1} можно взять в качестве искомого корня и остановиться
• Иначе: n = n + 1 и повтор шага.

 

3. Программная реализация (на языке C#)

 

Так выглядит моя программа (с комментариями!):

 

using System;

using System.Collections.Generic;

using System.Text;

namespace kyrsa4

{

    class Program

    {

        static void Main(string[] args)

        {

            //n - степень полинома

            Console.WriteLine("enter n");

            int n = Convert.ToInt32(Console.ReadLine());

            // List - список массивов из коэффицентов полиномов

            List<double[]> polinoms = new List<double[]>();

            double[] h0 = new double[1] {1};

            polinoms.Add(h0);

            double[] h1 = new double[2] {0,2};

            polinoms.Add(h1);

            for (int i = 2; i < n + 1; i++)

            {

                double[] hi = new double[i + 1];

                hi[0] = polinoms[i-2][0]*(-2*i+2);

                hi[i - 1] = polinoms[i - 1][i - 2]*2;

                hi[i] = polinoms[i - 1][i - 1]*2;

                for (int j = 1; j < i-1; j++)

                {

                 hi[j] = 2*polinoms[i - 1][j-1] + (-2*i+2)*polinoms [i-2][j];

                }

                polinoms.Add(hi);

           }

            //количество корней(roots - корни)

            int k = 0;

      //если степень многочлена нечетная, то обязательно есть корень,равный 0

            double [] roots = new double [n];

            if ((n & 1) == 1)

            {

               roots[0] = 0;

                k = 1;

            }

            //поиск корней

            double step = 0.1;

            int num = 1;

            while(k < n)

            {

                if (Math.Sign(f(num * step, polinoms[n])) != Math.Sign(f((num + 1) * step, polinoms[n])))

                {

                roots[k] = koren(num * step, polinoms[n], polinoms[n - 1]);

                roots[k + 1] = -roots[k];

                k += 2;

                }

                num++;

            }

            for (int i = 0; i < n; i++)

            {

                Console.WriteLine("root = " + roots[i]);

            }

            Console.ReadLine();

        }

        /// <summary>

        /// построение функции, эквивалентной полиному Эрмита

        /// </summary>

        /// <param name="x">параметр, передающийся функции</param>

        /// <param name="hn">массив из коэффициентов полинома</param>

        /// <returns>значение полинома в точке х</returns>

        static double f(double x, double[] hn)

        {

            if (x == 0)

            {

                return hn[0];

            }

            else

            {

                double pol = 0;

                for (int i = 0; i < hn.Length; i++)

                {

                    pol += Math.Sign(x)*hn[i] * Math.Exp(i * Math.Log(Math.Abs(x)));

                }

                return pol;

            }

        }

        /// <summary>

        /// производная от функции

        /// </summary>

        /// <param name="x">параметр, передающийся производной</param>

        /// <param name="hn_1">массив из коэффициентов полинома степени на 1 ниже</param>

        /// <returns>производную</returns>

        static double dfdx(double x, double[] hn_1)

        {

            if (hn_1.Length == 1)

            {

                return 2;

            }

            else

            {

                return 2 * f(x, hn_1) * hn_1.Length;

            }

        }

        /// <summary>

        /// приближение

        /// </summary>

        /// <param name="x">параметр, передающийся функции</param>

        /// <param name="hn">массив из коэффициентов полинома степени n</param>

        /// <param name="hn_1">массив из коэффициентов полинома степени n - 1</param>

        /// <returns>последовательность приближений к корню</returns>

        static double koren(double x, double[] hn, double[] hn_1)

        {

            while (Math.Abs(f(x, hn)) > 0.000001)

            {

                Console.WriteLine("x = " + x);

                Console.WriteLine("f(x)=" + f(x,hn));

                x -= f(x,hn) / dfdx(x,hn_1);

            }

            return x;

        }

   

}}

Начальное приближение: x₀ = 0.1

Погрешность 0.000001

Свойством корней полиномов  Эрмита является то, что они симметричны  относительно 0, однако я решила найти  и положительный корень, и отрицательный.

 

Результаты работы для разных степеней:

 

(при погрешности 0.000001)

 

enter n

5

root = 0

root = 0,95857246483967

root = -0,95857246483967

root = 2,02018287046078

root = -2,02018287046078

 

 

enter n

10

root = 0,342901327223768

root = -0,342901327223768

root = 1,03661082978951

root = -1,03661082978951

root = 1,75668364929988

root = -1,75668364929988

root = 2,53273167423279

root = -2,53273167423279

root = 3,43615911883774

root = -3,43615911883774

 

 

enter n

11

root = 0

root = 0,6568095668821

root = -0,6568095668821

root = 1,32655708449493

root = -1,32655708449493

root = 2,02594801582576

root = -2,02594801582576

root = 2,78329009978165

root = -2,78329009978165

root = 3,66847084655958

root = -3,66847084655958

 

(при погрешности 0.01)

enter n

15

root = 0

root = 0,565069583255576

root = -0,56506958325557

root = 1,13611558521092

root = -1,13611558521092

root = 1,71999257518837

root = -1,71999257518837

root = 2,32573248617395

root = -2,32573248617395

root = 2,96716692790528

root = -2,96716692790528

root = 3,66995037340445

root = -3,66995037340445

root = 4,4999907073094

root = -4,4999907073094

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Заключение:

 

Приведенные выше результаты получены при разных значениях погрешности.

 

Метод Ньютона сходится для полиномов до 11 степени при  погрешности 0.000001, и с погрешностью 0.01 сходится для полиномов до 15 степени.

 

Для полиномов больше 15 степени метод Ньютона зацикливается.

Объясняется это тем, что коэффициенты полинома становятся очень большими:

Полином 16 степени имеет  следующие коэффициенты:

k	ak
0	518918400
1	0
2	-8302694400
3	0
4	19372953600
5	0
6	-15498362880
7	0
8	5535129600
9	0
10	-984023040
11	0
12	89456640
13	0
14	-3932160
15	0
16	65536

 

H_n (c) = a_k c^k

Ошибка:| a_k | * |c|^k *e, | c^k | 1 – для каждого члена, где

e – машинная точность

 

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

Для достижения достаточно высокой точности значение полиномов Эрмита нужно вычислять не через коэффициенты степенного разложения, а, например, по рекуррентной формуле. Как это сделано в курсовой работе Анатолия Кондратьева.

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

 

Бахвалов, Жидков, Кобельков «Численные методы»

 

http://ru.wikipedia.org/wiki/Метод_Ньютона

 

http://ru.wikipedia.org/wiki/Полиномы_Эрмита

 

http://fr.wikipedia.org/wiki/Polynôme_d'Hermite

 

+  конспект по вычислительной  математике