Метод парабол для вычисления корней. Метод трапеций. Остаточный член формулы Симпсона равен
Метод секущих можно рассматривать как замену функции интерполяционным многочленом первой степени, проведенным по узлам
По трем последним итерациям можно построить интерполяционный многочлен второй степени, т. е. заменить график функции параболой. Запишем интерполяционный многочлен в форме Ньютона
Приравнивая его нулю, получим квадратное уравнение
Тот из двух корней квадратного уравнения (36), который меньше по модулю, определяет новое приближение
Очевидно, для начала расчета надо задать три первых приближения (обычно наугад выбирают три числа), т. е. процесс является трехшаговым.
Метод парабол построен по образцу методов третьего порядка. Однако замена производных разделенными разностями приводит к существенному уменьшению скорости сходимости. Рассуждениями, аналогичными рассуждениям в п. 7, можно показать, что вблизи простого корня выполняется соотношение
т. е. сходимость даже медленнее квадратичной. Вблизи кратного корня сходимость еще медленнее (хотя и более быстрая, чем линейная). Заметим, что строить аналогичные методы с использованием интерполяционного многочлена еще более высокой степени невыгодно: сходимость все равно будет медленней квадратичной, а расчет сильно усложняется.
В методе парабол «разболтка» счета вблизи корня сказывается еще сильней, чем в методе секущих, ибо в расчете участвуют вторые разности. Тем не менее корни можно найти, с хорошей точностью; для определения оптимального числа итераций удобно пользоваться приемом Гарвика, описанном в п. 7.
Метод парабол имеет важное достоинство. Даже если все предыдущие приближения действительны, уравнение (36) может привести к комплексным числам. Поэтому процесс может естественно сойтись к комплексному корню исходного уравнения. В методах простых итераций, касательных или секущих для сходимости к комплексному корню может потребоваться задание комплексного начального приближения (если ) вещественна при вещественном аргументе).
Корни многочлена. Метод парабол оказался исключительно эффективным для нахождения всех корней многочлена высокой степени. Если - алгебраический многочлен, то, хотя сходимость метода при произвольном начальном приближении и не доказана, на практике итерации всегда сходятся к какому-нибудь корню, причем быстро.
Для многочлена частное есть тоже многочлен; поэтому последовательно удаляя найденные корни, можно найти все корни исходного многочлена.
Замечание 1. Если - многочлен высокой степени, то возникают дополнительные трудности. Многочлен быстро возрастает при увеличении аргумента, поэтому в программе для ЭВМ должна быть страховка от переполнения. Обычно вводят масштабные множители, величина которых связана с диапазоном изменения аргумента.
Замечание 2. Наибольшие по модулю корни многочлена высокой степени могут быть очень чувствительны к погрешности коэффициентов при старших степенях. Например, корнями многочлена
являются последовательные целые числа слегка измененный многочлен имеет такие корни:
(здесь приведен только один знак после запятой). Кратные или близкие корни могут быть слабо устойчивыми даже при меньших степенях многочлена.
Замечание 3. Для удаления вычисленных корней надо... делить многочлен. Это вносит погрешность округления в коэффициенты и влияет на точность нахождения следующих корней. На практике отмечено, что если сначала удалять меньшие по модулю корни, точность падает мало, но если надать удаление с больших корней, точность может упасть катастрофически. Поэтому за начальное приближение берут тогда итерации обычно сходятся к наименьшему по модулю корню. Его удаляют и по такому же начальному приближению ищут следующий корень и т. д. При такой организации вычислений потеря точности будет небольшой.
Метод золотого сечения
Рассмотрим такое симметричное расположение точек на отрезке [а; b] , при котором одна из них становится пробной точкой и на новом отрезке, полученном после исключения части исходного отрезка. Использование таких точек позволяет на каждой итерации метода исключения отрезков, кроме первой, ограничиться определением только одного значения , так как другое значение уже найдено на одной из предыдущих итераций.
Точки которые обладают следующим свойством: каждая делит отрезок [а; b] на две неравные части так, что отношение длины всего отрезка к длине его большей части равно отношению длин большей и меньше частей отрезка. Точки с таким свойством называются точками золотого сечения отрезка [а; b] . Это и объясняет название рассматриваемого метода.
Опишем алгоритм метода золотого сечения.
Шаг 1. Найти по формулам . Вычислить . Положить .
Ш а г 2. Проверка на окончание поиска: если , то перейти к шагу 3, иначе - к шагу 4.
Шаг 3. Переход к новому отрезку и новым пробным точкам. Если , то положить и вычислить , иначе - положить и вычислить .
Положить и перейти к шагу 2.
Ш а г 4. Окончание поиска: положить .
Поиск точки минимума методами исключения отрезков основан на сравнении значений функции в двух точках. При таком сравнении разности значений f(x) в этих точках не учитываются, важны только их знаки.
Учесть информацию, содержащуюся в относительных изменениях значений f(x) в пробных точках, позволяют методы полиномиальной аппроксимации , основная идея которых состоит в том, что для функции f(x) строится аппроксимирующий многочлен и его точка минимума служит приближением к х*. Для эффективного использования этих методов на функцию f(x), кроме унимодальности, налагается дополнительное требование достаточной гладкости (по крайней мере, непрерывности).
Для повышения точности аппроксимации можно, во-первых, увеличивать порядок полинома и, во-вторых, уменьшать длину отрезка аппроксимации. Первый путь приводит к быстрому усложнению вычислительных процедур, поэтому на практике используются аппроксимирующие полиномы не выше третьего порядка. В то же время уменьшение отрезка, содержащего точку минимума унимодальной функции, не представляет особого труда.
В простейшем методе полиномиальной аппроксимации - методе парабол используются полиномы второго порядка. На каждой итерации этого метода строится квадратный трехчлен, график которого (парабола) проходит через три выбранные точки графика функции f(x) (рис. 2).
Опишем метод парабол. Рассмотрим унимодальную на отрезке [а; b] функцию f(x) , достигающую минимума во внутренней точке этого отрезка. Выберем три точки отрезка [а; b] , для которых выполняются неравенства
Рис. 2. Иллюстрация к методу парабол
Из унимодальности f(x) следует, что . Построим квадратный трехчлен , график которого проходит через точки графика функции f(x) . Будем считать, что хотя бы одно из неравенств (3) для является строгим (если , то поиск точки х * на этом закончен, так как из унимодальности функции f(x) следует, что она достигает минимума в каждой точке отрезка ). Тогда из (3) следует, что ветви искомой параболы направлены вверх, а точка минимума трехчлена принадлежит отрезку .
Определяя коэффициенты из системы уравнений
Точку минимума х квадратного трехчлена q(x) вычислим, приравняв его производную к нулю. Получим
Число х из (4) служит очередным приближением метода парабол к х *. Далее описанная процедура повторяется для новых точек , удовлетворяющих неравенствам (3).
Выбрать эти точки среди и можно с помощью перехода от исходного к новому отрезку , содержащему точку х *, методом исключения отрезков. Для этого перехода используются пробные точки и и сравниваются значения в этих точках. Начало и конец нового отрезка, а также пробная точка, попавшая на него, образуют тройку точек, обладающих свойством (3).с числом . Если , то поиск завершить, полагая , иначе - перейти к шагу 4.
Ш а г 4. Вычислить значение . Перейти к шагу 5.
Шаг 5. Определить новую тройку чисел . Присвоить соответствующие значения f(x), найденные ранее. Перейти к шагу 2.
Метод трапеций
Разобьем отрезок на равных частей при помощи точек:
Метод трапеций заключается в замене интеграла суммой:
Абсолютная погрешность приближения, полученного по формуле трапеций, оценивается с помощью формулы, где.
Метод парабол (метод Симпсона)
а) Через любые три точки с координатами проходит только одна парабола.
б) Выразим площадь под параболой на отрезке через:
Учитывая значения и из пункта а) следует:
в) Разобьем отрезок на равных частей при помощи точек:
Метод парабол заключается в замене интеграла суммой:
Для приближенных практических расчетов применяется формула:
Абсолютная погрешность вычисления по формуле (4) оценивается соотношением, где.
Оценка точности вычисления «неберущихся» интегралов
В данной работе вычисление абсолютной и относительной погрешности проводится при условии, что известно точное значение определенного интеграла. Однако не всякая первообразная, даже тогда, когда она существует, выражается в конечном виде через элементарные функции. Таковы первообразные, выраженные интегралами, и т.д. Во всех подобных случаях первообразная представляет собой некоторую новую функцию, которая не сводится к комбинации конечного числа элементарных функций.
Определенные интегралы от таких функций можно вычислить только приближенно. Для оценки точности вычисления в таких случаях используют, например, правило Рунге. В данном случае интеграл вычисляется по выбранной формуле (прямоугольников, трапеций, парабол Симпсона) при числе шагов, равном n, а затем при числе шагов, равном. Погрешность вычисления значения интеграла при числе шагов, равном, вычисляется по формуле Рунге:, для формул прямоугольников и трапеций, а для формулы Сипсона. Таким образом, интеграл вычисляется для последовательных значений числа шагов, ..., где - начальное число шагов. Процесс вычислений заканчивается, когда для очередного значения будет выполнено условие, где - заданная точность.
Для того чтобы не вычислять один и тот же интеграл по нескольку раз для разных разбиений отрезка интегрирования, можно вычислить шаг интегрирования заранее.
Пример. Выбрать шаг интегрирования для вычисления интеграла с точностью 0,01 пользуясь квадратурными формулами прямоугольников, трапеций, Симпсона.
Квадратурная формула прямоугольников.
Вычислим, при каком шаге погрешность будет составлять 0,01:
подынтегральный трапеция парабола неберущийся
Поскольку, то.
При шаге отрезок разбивается на равностоящих узлов.
Квадратурная формула трапеций.
Поскольку, .
При шаге,отрезок разбивается на равностоящих узлов.
Квадратурная формула Симпсона.
Вычислим, при каком шаге погрешность составит 0,01:
При шаге, отрезок разбивается на равностоящих узлов.
Как и следовало ожидать, наименьшее количество равностоящих узлов получается при вычислении интеграла по квадратурной формуле Симпсона.
Студенту предлагается работа, состоящая из четырех этапов:
- 1 этап - точное вычисление определенного интеграла.
- 2 этап - приближенное вычисление определенного интеграла одним из методов: прямоугольников или трапеций.
- 3 этап - приближенное вычисление определенного интеграла методом парабол.
4 этап - расчет и сравнение абсолютной и относительной ошибок приближенных методов: , где - точное решение интеграла, - значение интеграла, полученное с помощью приближенных методов.
Построение графика подынтегральной функции.
Варианты и образец выполнения РГР приведены ниже.
Варианты
|
№ варианта |
||||
Образец выполнения РГР
Задание. Вычислить интеграл
1. Точное вычисление:
2. Приближенное вычисление с помощью формул прямоугольников:
Составим таблицу:
По первой формуле прямоугольников получаем:
0,1 = 0,1·3,062514 = 0,306251.
По второй формуле прямоугольников получаем:
0,1 = 0,1· 4,802669 = 0,480267.
В данном случае первая формула дает значение интеграла с недостатком, вторая - с избытком.
3. Приближенное вычисление по формуле трапеций:
В нашем случае получаем:
0,1 = =0,1 = 0,1·4,095562 = =0,409556.
Вычислим относительную и абсолютную погрешности.
4. Приближенное вычисление по формуле Симпсона:
В нашем случае получаем:
Вычислим относительную и абсолютную погрешности.
В действительности, = 0,40631714.
Таким образом, при разбиении отрезка на 10 частей по формуле Симпсона мы получили 5 верных знаков; по формуле трапеций - три верных знака; по формуле прямоугольников мы можем ручаться только за первый знак.
Для нахождения определенного интеграла методом трапеций площадь криволинейной трапеции также разбивается на n прямоугольных трапеций с высотами h и основаниями у 1 , у 2 , у 3 ,..у n , где n - номер прямоугольной трапеции. Интеграл будет численно равен сумме площадей прямоугольных трапеций (рисунок 4).
Рис. 4
n - количество разбиений
Погрешность формулы трапеций оценивается числом
Погрешность формулы трапеций с ростом уменьшается быстрее, чем погрешность формулы прямоугольников. Следовательно, формула трапеций позволяет получить большую точность, чем метод прямоугольников.
Формула Симпсона
Если для каждой пары отрезков построить многочлен второй степени, затем проинтегрировать его на отрезке и воспользоваться свойством аддитивности интеграла, то получим формулу Симпсона.
В методе Симпсона для вычисления определенного интеграла весь интервал интегрирования разбивается на подинтервалы равной длины h=(b-a)/n. Число отрезков разбиения является четным числом. Затем на каждой паре соседних подинтервалов подинтегральная функция f(x) заменяется многочленом Лагранжа второй степени (рисунок 5).
Рис. 5 Функция y=f(x) на отрезке заменяется многочленом 2-го порядка
Рассмотрим подынтегральную функцию на отрезке. Заменим эту подынтегральную функцию интерполяционным многочленом Лагранжа второй степени, совпадающим с y= в точках:
Проинтегрируем на отрезке.:
Введем замену переменных:
Учитывая формулы замены,
Выполнив интегрирование, получим формулу Симпсона:
Полученное для интеграла значение совпадает с площадью криволинейной трапеции, ограниченной осью, прямыми, и параболой, проходящей через точки На отрезке формула Симпсона будет иметь вид:
В формуле параболы значение функции f(x) в нечетных точках разбиения х 1 , х 3 , ..., х 2n-1 имеет коэффициент 4, в четных точках х 2 , х 4 , ..., х 2n-2 - коэффициент 2 и в двух граничных точках х 0 =а, х n =b - коэффициент 1.
Геометрический смысл формулы Симпсона: площадь криволинейной трапеции под графиком функции f(x) на отрезке приближенно заменяется суммой площадей фигур, лежащих под параболами.
Если функция f(x) имеет на непрерывную производную четвертого порядка, то абсолютная величина погрешности формулы Симпсона не больше чем
где М - наибольшее значение на отрезке . Так как n 4 растет быстрее, чем n 2 , то погрешность формулы Симпсона с ростом n уменьшается значительно быстрее, чем погрешность формулы трапеций.
Вычислим интеграл
Этот интеграл легко вычисляется:
Возьмем n равным 10, h=0.1, рассчитаем значения подынтегральной функции в точках разбиения, а также полуцелых точках.
По формуле средних прямоугольников получим I прям =0.785606 (погрешность равна 0.027%), по формуле трапеций I трап =0.784981 (погрешность около 0,054. При использовании метода правых и левых прямоугольников погрешность составляет более 3%.
Для сравнения точности приближенных формул вычислим еще раз интеграл
но теперь по формуле Симпсона при n=4. Разобьем отрезок на четыре равные части точками х 0 =0, х 1 =1/4, х 2 =1/2, х 3 =3/4, х 4 =1 и вычислим приближенно значения функции f(x)=1/(1+x) в этих точках: у 0 =1,0000, у 1 =0,8000, у 2 =0,6667, у 3 =0,5714, у 4 =0,5000.
По формуле Симпсона получаем
Оценим погрешность полученного результата. Для подынтегральной функции f(x)=1/(1+x) имеем: f (4) (x)=24/(1+x) 5 , откуда следует, что на отрезке . Следовательно, можно взять М=24, и погрешность результата не превосходит величины 24/(2880 4 4)=0.0004. Сравнивая приближенное значение с точным, заключаем, что абсолютная ошибка результата, полученного по формуле Симпсона, меньше 0,00011. Это находится в соответствии с данной выше оценкой погрешности и, кроме того, свидетельствует, что формула Симпсона значительно точнее формулы трапеций. Поэтому формулу Симпсона для приближенного вычисления определенных интегралов используют чаще, чем формулу трапеций.
Кафедра «Высшей математики»
Выполнил: Матвеев Ф.И.
Проверила: Бурлова Л.В.
Улан-Удэ.2002
1.Численные методы интегрирования
2.Вывод формулы Симпсона
3.Геометрическая иллюстрация
4.Выбор шага интегрирования
5.Примеры
1. Численные методы интегрирования
Задача численного интегрирования заключается в вычислении интеграла
посредством ряда значений подынтегральной функции .Задачи численного интегрирования приходится решать для функций, заданных таблично, функцией, интегралы от которых не берутся в элементарных функциях, и т.д. Рассмотрим только функции одной переменной.
Вместо функции, которую требуется проинтегрировать, проинтегрируем интерполяционный многочлен. Методы, основанные на замене подынтегральной функции интерполяционным многочленом, позволяют по параметрам многочлена оценить точность результата или же по заданной точности подобрать эти параметры.
Численные методы условно можно сгруппировать по способу аппроксимации подынтегральной функции.
Методы Ньютона-Котеса основаны на аппроксимации функции
полиномом степени . Алгоритм этого класса отличается только степенью полинома. Как правило, узлы аппроксимирующего полинома – равноотносящие.Методы сплайн-интегрирования базируются на аппроксимации функции
сплайном-кусочным полиномом.В методах наивысшей алгебраической точности (метод Гаусса) используются специально выбранные неравноотносящие узлы, обеспечивающие минимальную погрешность интегрирования при заданном (выбранном) количестве узлов.
Методы Монте-Карло используются чаще всего при вычислении кратных интегралов, узлы выбираются случайным образом, ответ носит вероятностный характер.
суммарная погрешность погрешность усечения
погрешность округления
Независимо от выбранного метода в процессе численного интегрирования необходимо вычислить приближенное значение интеграла и оценить погрешность. Погрешность уменьшается при увеличении n-количества
разбиений отрезка
. Однако при этом возрастает погрешность округленияза счет суммирования значений интегралов, вычисленных на частичных отрезках.
Погрешность усечения зависит от свойств подынтегральной функции и длины
частичного отрезка.2. Вывод формулы Симпсона
Если для каждой пары отрезков
построить многочлен второй степени, затем проинтегрировать его и воспользоваться свойством аддитивности интеграла, то получим формулу Симпсона. Рассмотрим подынтегральную функцию на отрезке . Заменим эту подынтегральную функцию интерполяционным многочленом Лагранжа второй степени, совпадающим с в точках :Проинтегрируем
:и называется формулой Симпсона.
Полученное для интеграла
значение совпадает с площадью криволинейной трапеции, ограниченной осью , прямыми , и параболой, проходящей через точкиОценим теперь погрешность интегрирования по формуле Симпсона. Будем считать, что у
на отрезке существуют непрерывные производные . Составим разностьК каждому из этих двух интегралов уже можно применить теорему о среднем, поскольку
непрерывна на и функция неотрицательна на первом интервале интегрирования и неположительна на втором (то есть не меняет знака на каждом из этих интервалов). Поэтому:(мы воспользовались теоремой о среднем, поскольку
- непрерывная функция; ).Дифференцируя
дважды и применяя затем теорему о среднем, получим для другое выражение: , гдеИз обеих оценок для
следует, что формула Симпсона является точной для многочленов степени не выше третьей. Запишем формулу Симпсона, напрмер, в виде: , .Если отрезок
интегрирования слишком велик, то его разбивают на равных частей (полагая ), после чего к каждой паре соседних отрезков , ,..., применяют формулу Симпсона, именно:Запишем формулу Симпсона в общем виде.
