Практикум j практическое примщенше численных методов

Для оценки начального приближения используется график исследуемой функции 10(т₂ - х\)² + (1 — Xi)² с использованием следующей программы.
ехег - 8 2.ру
import пшпру as пр import matplotlib.pyplot as pit from grad import grad def F(x):
return 10. *(x[l] - x[0]**2)**2 + (1 - x[0])**2 def GradF(x):
gr = np.zeros((2),’float’)
gr[0] = -40.*(x[l] - x[0]**2)*x[0] - 2.*(1 - x[0]) gr[1] = 20.*(x[l] - x[0]**2) return gr
# graph of function x = np.linspace(-2., 2., 101) у = np.linspace(-l., 3., 101)
X, Y = np.meshgrid(x, y) z = F( [X, Y])
_v = np.linspace(0., 10., 21)
pit.contourf(x, y, z, v, cmap=plt.cm.gray)
pit .colorbarO
pit .show()
# minimum function
_x0 = np.array([0., 0.1])
xMin, nit = grad(F, GradF, xO)
print ’XMin:’, xMin
print ’Number of iterations = nit
xMin [ 0.99995383 0.99990305]
Щщ® Ш о f.I)iШШШ? ; ^::V::;^:;■^::
функция имеет выраженный овражный характер (рис. 8.2), что обуславлива­ет достаточно медленную сходимость градиентного метода.

4. 
   Задачи
   

Задача 8.1 Напишите программу для нахоэ1сдепия минимума функции од­ной переменной f(x) на интервале [а, Ь\ с использованием интерполяцион­ного полинома второго порядка. С помощью этой программы найдите два первых локальных минимума функции х² — 50siri(.x*) при х > 0.
Задача 8.2 Напишите программу для иахоэюдения локального минимума функции одной переменной f(x) методом Ньютона. С ее помощью найдите минимум функции 2х — 1 + 2cos(7rx) на интервале [0,2].
Задача 8.3 Напишите программу для нахоэюдения локального минимума функции многих переменных f(x) методом Ньютона. Продемонстрируйте работоспособность программы па задаче нахоэюдепия минимума функции х\ + х\ — 3xix₂, х_а > 0, а = 1,2 при различных начальных приблиэюепиях.
Упражнение 8.3 Напишите программу для иахоэюдепия минимума функ­ции одной переменной f(x) на интервале [а, Ь\ при ограничениях д(х) > 0 методом штрафа с использованием метода золотого сечения для решения задачи безусловной минимизации. С ее помощью найдите минимум функ­ции е~^хх при х >2.
Интерполирование и приближение функций
Рассматриваются задачи приближенного восстановления значений функции одной переменной по ее значениям в некоторых точках. Традиционный под­ход для одномерной интерполяции связан с построением алгебраических мно­гочленов, принимающих заданные значения в точках интерполяции. Более перспективными являются подходы с использованием кусочно-гладких поли­номов. Отдельно выделены задачи приближения функций в нормированных пространствах.

Основные обозначения
/по	— интерполируемая функция
Х0 < ... < хп	— узлы интерполирования
	— система Чебышева
ф)	— обобщенный интерполяционный
	многочлен
Ьп(х)	— интерполяционный многочлен
	п-го порядка
f (Xi, X{+i)	— разделенная разность первого порядка
f X{.|_i, . . . ,	— разделенная разность к-rо порядка
Sm(x)	— интерполяционный сплайн т-го порядка

1. 
   Задачи интерполяции и приближения функций
   

Задача интерполяции ставится следующим образом. Пусть на отрезке [а, Ь] в узлах интерполирования х₀ < < ... < х_п известны значения функции
Уг = f(xi), г = 0,1,... ,п. Необходимо найти значения функции f(x) в точках х Ф Xi, г = 0,1,..., п.
Пусть па отрезке [а, Ь] задана система функций {<£г(-^г’)}Г=о и определим
<Р(^Х) = Yj^Ci4>i{^x) (^9Л)
i=0
с действительными коэффициентами с*,г = 0,1,...,п. При интерполирова­нии функции f(x) для нахождения коэффициентов используются условия
4>(xi) =/(Xi), г = 0,1,..., n. (9.2)
В частном случае алгебраической интерполяции pi(x) = х\ г = 0,1,... ,п.
При интерполяции сплайнами функция f(x) приближается многочленами невысокой степени на частичных отрезках [х^х^i], где г = 0,1,... , п — 1.
Рассматривается также задача построения обобщенного многочлена (р{х) приближающего заданную функцию f(x). В линейном нормированном про­странстве коэффициенты обобщенного многочлена <р(х) определяются из условия минимальности нормы погрешности интерполирования:
ll/(*)-£г=0
Аналогично ставится задачи интерполяции и приближения многомерных функций.

2. 
   Алгоритмы интерполяции и приближения функций
   

Для одномерных функций задачи интерполяции решаются с использованием алгебраических многочленов Лагранжа и Ньютона, параболических и куби­ческих сплайнов, рассмотрена задача иаилучшего приближения в гильберто­вом пространстве.
Полиномиальная интерполяция
При аппроксимации полиномами используются функции 4>i( х)=х\ * = 0,1
и интерполяционный многочлен (см. (9.1)) имеет вид
<
Интерполяционный многочлен Лагранжа записывается в виде
и>(х)


Ln(x) = ^2


(^х ~ ^xiW{^xi)


f(^xi),


(9.4)

р(х) = L_n(x) = ^CiX¹.
где и(х) — многочлен степени п + 1:
п
<Ф) = П(а: - x_t),





Можно использовать другую запись интерполяционного многочлена в ви­де интерполяционного многочлена Ньютона, которая строится с помощью разделенных разностей. Разделенной разностью первого порядка называется отношение
/(a-'j+i) — f(xj)
■^i+l
Разделенная разность к-ro порядка определяется по рекуррентной формуле
/ %1) • • • ? 3Ci+k )
/(^г+1 ? *^г+2ч • • • > ^г+fc) f (^г? *^2+1 > • • • j ^i+k— 1)
З'г+А; ^’г
С использованием таких обозначений получим
•Мя) = f(^xo) + {х - ^xo)f{^xO,^xl) +
+{х - х₀){х - x₁)f(x₀,x-_i,x₂) + ...
... + {х- х₀)(х - Щ • • • (ж - x_n-i)f(x₀,xi,.. ,,х_п). (9.5)
Интерполяционные сплайны
Пусть функция f(x) задана в узлах а = x_Q < хi < ... < х_п = Ь. Интерполя­ционный сплайн S_m(x) порядка т определяется из условий:

1. 
   на каждом отрезке [xi,x_i+i],i = 0,1,... ,п — 1 S_m(x) является полиномом степени га;
   
2. 
   на всем отрезке [a, b] S_m(x) имеет непрерывные производные до порядка т — 1;
   
3. 
   в узлах интерполяции
   

*$тп(*^г) / (*^г) j ^ 0,1,-.-, ТХ.
При гп > 2 единственность S_m(x) обеспечивается гп — 1 дополнительным¹¹ условиями. Обычно эти условия формулируются на концах отрезка интерн⁰' ляции [а,Ь].
Интерполяционный кубический сплайн Ss(x) на отрезке [x^Xi+i] задается полиномом третьей степени:
5з^г) = Oi + Ы(х - Xi) + ^(х - Xi)² + j(x - xi)³,
X
(9.6)

i < x < x_i+i, i = 0,1,..., n - 1,
причем
a
dS?

_{ = S?(x i), h =

Численные 1
ЧИСЛЕННЫЕ МЕТОДЫ 3
Содержание 5
Программное обеспечение 9
Элементы языка 21
| ’G \\Vab\\Python\\Testl \\src ’ , ’C-\\Program Files \\ ■/ NetBeans 6 7\\python! ’ , ’С Д \ Windows\\system32\\ python26 zip ’ , ’C^YPytho^G^DLLs’ , /С \\Python26\\lib ’ , 39
Математический Python 44
I 3 .4.II. ■ 61
И 0 ] 61
vs = Е 104
= np.zeros((m), ’float’) for i in range(0, m): 115
Прямые методы линейной алгебры 160
Итерационные методы линейной алгебры 173
ъВ <А< 7₂в, Ъ > 0, (5.16) 179
Спектральные задачи линейной алгебры 185
Шп ^{уШ’^ук) = 1. 187
1||Й7б2ШШ&Ш 191
Нелинейные уравнения и системы 197
Задачи минимизации функций 206
/V) 207
Интерполирование и приближение функций 217
Численное интегрирование 228
Интегральные уравнения 239
Задача Коши для обыкновенных дифференциальных уравнений 252
= ^(/(Wi,r⁺¹) + /(*»,»”)). п = 0,1,... 253
-£ ^{= у}*' 1Г = И¹о < i < 100, 263
Краевые задачи для обыкновенных дифференциальных уравнений 265
М*)] = о, 266

Два дополнительных условия можно взять в виде (естественные кубические сплайны)
d²S?\ . _п (PS?-^l), ._Л „
^ш
dx²
{^хо) — 0, dx² (З'п) — 6.
Приближение функций в нормированном пространстве
П
/
•/а


(Ля) = / f{x)g(x)dx,



1/2

усть Н — вещественное гильбертово пространство со скалярным произве­дением (/,#) и нормой ||/|| = (/, Z)¹/²- В случае Я = L₂(a,6) имеем
В задаче о наилучшем приближении по системе функций
y?i(z) Е Я, г = 0,1,..., п
строится обобщенный многочлен (9.1) (элемент наилучшего приближения), который для заданной приближаемой функции f(x) Е Я минимизирует нор­му отклонения (9.3).
Коэффициенты элемента наилучшего приближения находятся из решении следующей системы линейных уравнений:
£ф_иъ) = (Ш, г = 0,1 (9.7)
j=О

3. 
   Упражнения
   

Упражнение 9.1 Напишите программу для интерполирования данных на основе интерполяционного многочлена Ньютона. С помощью этой програм­мы интерполируйте данные в равноотстоящих узлах для функции Руиге f(x) = (1 + 25х²)~¹ на интервале [-1,1] при п = 4, б, 10.
В модуле interpolation функция coef () предназначена для вычисления коэф­фициентов интерполяционного многочлена Ньютона, а функция interpola­tion О — для вычисления значения интерполяционного полинома в заданной точке.
Hisiiiiiiisis
def interpolation^, х, х0):
к и и
Evaluates Newton’s polynomial at xO.
и и и

• 
  Degree of polynomial n = len(x) - 1
  

yO = c[n]
for k in ranged,n+1):
yO = c[n-k] + (xO - x[n-k]) * yO return yO def coef(x, y):
и и и
Computes the coefficients of Newton’s polynomial.
и и и

• 
  Number of data points m = len(x)
  

с = у.copy()
for k in ranged,m):
c[k:m] = (c[k:m] - c[k-l])/(x[k:m] - x[k-l]) return c
Решение задачи полиномиальной интерполяция для функции Рунге дается следующей программой.
import numpy as np
i



Рис. 9.1 Интерполяция функции Рунге f(x) = (1 + 25т²) ¹

mport matplotlib.pyplot as pit
from interpolation import interpolation, coef
def f(x):
return 1. / (1 + 25*x**2) a = -l. b = 1.
^X1 - np.linspace(a, b, 200)
У1 = f (x 1) pit.plot(xl, yl) mist = [4, 6, 10] sglist = [’ —\ »:»]
k in range(len(nList)): n = nList[k]
x = np.linspace(a, b, n+1)
У = f(x)
pit.scatter(x, у, marker^ o’) c = coef(x, y)
yl = interpolation^, x, xl) si = ’n=^J + str(n)