ЧМ_Билеты. 1. Основные характеристики численных методов. Взаимосвязь характеристик

• Название: 1. Основные характеристики численных методов. Взаимосвязь характеристик
• Дата: 26.02.2018
• Размер: 1.85 Mb.
• Имя файла: ЧМ_Билеты.pdf
• Тип: Документы; #37249
• страница: 2 из 5

1.
Вычислить
)
(a
f
fa 
и
).
(b
f
fb 
2.
Вычислить c по формуле (1) и
).
(c
f
fc 
3.
Если знаки
fa
и
fc
совпадают, т.е.
)),
(
(
))
(
(
a
f
sign
c
f
sign

то конец b неподвижен. В этом случае приняты:
,
c
a 
,
fc
fa 
если


 c
b
. Затем перейти к п.2. В противном случае, т.е. при


c
b 
вычисления завершены, т.к. заданная точность достигнута.
4.
Если
,
0
*

fc
fa
неподвижен конец a . В случае


 a
c
:
,
c
b 
fc
fb 
Затем перейти к п.2. Иначе – вычисления завершены. Значение c используется как корень уравнения.
Достоинства метода хорд: 1) абсолютно надежен; 2) в большинстве случаев имеет более быструю сходимость, чем метод деления пополам.
Недостаток: скорость сходимости зависит от вида
)
(x
f
, и поэтому для некоторых функций число шагов на уточнение корня может оказаться большим, чем в методе деления пополам.
Рис.1.5 – иллюстрация к методу хорд
x
y
a
b
)
(a
f
)
(b
f
0
x
c
0
y
)
(c
f
'
c
b
границы
перенос
)
(x
f
*
x
хорда
я

1
хорда
я

2
A
B

12
5.
. Иллюстрация и алгоритм метода касательных.
Если
)
(x
f
имеет одну и более непрерывных производных (т.е.
)
(x
f
достаточно гладкая), то можно применить метод Ньютона (метод касательных) и метод секущих, позволяющие сократить число вычислений функции по сравнению с методом деления пополам и методом хорд, т.е. уменьшить затраты машинного времени.
В методе Ньютона каждое новое приближение
1

k
x
вычисляется как единственный нуль касательной прямой к функции
)
(x
f
в точке
k
x
:
),
(
/
)
(
1
k
k
k
k
x
f
x
f
x
x




,
0
)
(


k
x
f
2
,
1
,
0

k

Это итерационная формула метода Ньютона. Каждая итерация требует вычисления не только
)
(x
f
, но и её производной
)
( x
f 
.
Рис.1.6 – алгоритм метода хорд
начало

,
, b
a
2
),
(
),
(



n
b
f
fb
a
f
fa







n
c
f
fc
a
b
fa
fb
fa
a
c
),
(
)
(
0
*

fc
fa


c
b 


a
c 
конец
fc
fa
c
a


fc
fb
c
b


да
да
n
fc
c
,
,
,

да

13
Иллюстрация к методу касательных представлена на рис.1.7, а алгоритм метода – на рис.1.8.
Метод Ньютона обладает хорошей сходимостью. Основная трудность заключается в выборе начального приближения
,
0
x
которое ведет к сходящемуся итерационному процессу. Поэтому методу Ньютона часто предшествует какой-нибудь глобально сходящийся алгоритм типа деления пополам.
Рис.1.7 – иллюстрация к методу касательных
x
y
0
x
)
0
(x
f
1
t
)
(x
f
1
x
2
t
2
x
)
1
(x
f
*
x
)
2
(x
f
я
касательна
я

1
я
касательна
я

2

14
6.
Иллюстрация и алгоритм метода секущих.
Метод секущих
Данный метод заменяет производную первой разностью, найденной по двум последним итерациям. Итерационная формула метода имеет вид
,
/
)
(
1
k
k
k
k
s
x
f
x
x



),
/(
))
(
)
(
(
1 1





k
k
k
k
k
x
x
x
f
x
f
s
,...,
2
,
1

k
0
)
(
*
)
(
1 0

x
f
x
f
В этом алгоритме начинают с двумя исходными числами
0
x
и .
1
x На каждом шаге
1

k
x
получают как единственный нуль секущей прямой к функции
),
(x
f
проходящей через точки с абсциссами
1

k
x
и
k
x
(рис.1.9). Алгоритм метода секущих приведен на рис.1.10
Метод секущих имеет хорошую сходимость. Недостаток - в назначении
0
x
и
1
x
, достаточно близких к корню для того, чтобы могла начаться сходимость.
Рис.1.8 – алгоритм метода касательных
начало

,
0
x
0
,
0


n
x
x
t
x
n
x
f
x
f
t





,
2
),
(
/
)
(
'


t
да
1
),
(
,
,

n
x
f
x

конец

15
Рис.1.9 – иллюстрация к методу секущих
x
y
a
b
a
x 
0
b
x 
1 2
x
3
x
4
x
1
y
)
(x
f
секущая
я

1
секущая
я

2 0
y
секущая
я

3
*
x
Рис.1.10 – алгоритм метода секущих
начало

,
, b
a
2
),
1
(
1
),
0
(
0
,
1
,
0





n
x
f
y
x
f
y
b
x
a
x










n
x
f
y
y
y
t
x
x
x
x
x
y
y
y
t
),
1
(
1
,
1 0
,
1
,
1 0
,
)
0 1
0 1
(
1


t
да
n
y
x
,
1
,
1
,

конец

16
7.
Иллюстрация и алгоритм метода итераций.
Метод итераций
Уравнение
0
)
(

x
f
заменяют равносильным
).
(x
x


Выбирают каким-либо способом приближенное значение корня
0
x
и по нему находят
).
(
0 1
x
x


Повторяя процесс, получают последовательность чисел:
),
(
1


n
n
x
x

,
2
,
1

n
Если эта последовательность - сходящаяся, то предел



n
n
x
x
lim
*
является корнем равносильного уравнения и может быть вычислен по итерационной формуле
),
(
1


n
n
x
x

,
2
,
1

n
с любой степенью точности.
Процесс итераций следует продолжать до тех пор, пока для двух последовательных приближений не будет выполнено неравенство.
,
/
)
1
(
|
|
1
q
q
x
x
n
n





где

- заданная абсолютная точность вычисления корня и
|
)
(
|
'
x
q


Поэтому в методе итераций при переходе от уравнения
0
)
(

x
f
к уравнению
)
(x
x


следует выбирать такое представление
)
(x
x


, при котором
,
1
|
)
(
|



q
x

что является условием сходимости метода Чем меньше q  тем быстрее последовательные приближения сходятся к корню
*
x

Иллюстрации к методу итераций даны на рис.1.11, алгоритм – на рис.1.12
В заключение следует отметить что не существует метода который имел бы явное преимущество перед остальными для произвольного класса функций

17
Рис.1.11а,б – иллюстрации к методу итераций
x
y
)
(x
x


x
y 
)
(x
y


0
x
1
x
2
x
*
x
б)
"
"спираль
процесс
x
y
)
(x
x


x
y 
)
(x
y


0
x
1
x
2
x
*
x
a)
"
" лестница
процесс

18
8.
Алгоритм комбинированного метода хорд и касательных.
Комбинированный метод хорд и касательных
Методы хорд и касательных дают приближения корня с разных сторон. Поэтому их часто применяют в сочетании друг с другом, тогда уточнение корня происходит быстрее.
Пусть дано уравнение f(x) = 0, корень отделен на отрезке [a, b].
Рассмотрим случай, когда f ‘(x) f ’’(x)>0 (рис. 2.13).
Рис. 2.13
Рис.1.12 – алгоритм метода итераций
начало

,
0
x
0
,
0


n
x
x



n
x
x
),
(
1



 x
x1 1
x
x 
конец
1
),
1
(
,
1
,

n
x
f
x

да

19
В этом случае метод хорд дает приближенное значение корня с недостатком
(конец b неподвижен), а метод касательных – с избытком (за начальное приближение берем точку b).
Тогда вычисления следует проводить по формулам:
Теперь корень ξ заключен в интервале [a
1
, b
1
]. Применяя к этому отрезку комбинированный метод, получим: и т.д.
(2.6)
Если же f ‘(x) f ’’(x)<0 (рис. 2.14), то, рассуждая аналогично, получим следующие формулы для уточнения корня уравнения:
Рис. 2.14

20
Вычислительный процесс прекращается, как только выполнится условие:
9.
Алгоритм комбинированного метода деления пополам и итераций.
Рис.1.13 – алгоритм комбинированного метода хорд и касательных
начало

,
, b
a
2
),
(
),
(



n
b
f
fb
a
f
fa







n
c
f
fc
a
b
fa
fb
fa
a
c
),
(
)
(
0
*

fc
fa


 b
a
конец









n
b
f
fb
fc
fa
c
a
n
b
f
fb
b
),
(
,
,
,
,
)
(
'









n
a
f
fa
fc
fb
c
b
n
a
f
fa
a
),
(
,
,
,
,
)
(
'
да
1
),
2
(
,
2
,



n
b
a
f
b
a

да

21
10.
Алгоритм расчета зависимости затрат машинного времени от
задаваемой ошибки в методах уточнения корней нелинейных уравнений.
Замеряй через цикл
11.
Интерполяция и экстраполяция. Постановка задачи интерполяции.
Методы интерполяции (перечислить)

22
Интерполяция – это нахождение по ряду данных значений функции промежуточных её значений. Экстраполяция позволяет найти значения функции вне интервала интерполяции. Исходными данными для решения задач интерполяции и экстраполяции являются значения таблично заданной функции:
x
0
x
1
x
….
i
x
….
n
x
y
0
y
1
y
….
i
y
….
n
y
Узлы интерполяции могут быть неравноотстоящими
i
i
i
h
x
x


1
и равноотстоящими
h
x
x
i
i


1
, где
h
h
i
,
- шаг интерполяции.
Решением задачи интерполяции (экстраполяции) является интерполирующая
(экстраполирующая) функция
)
(x
F
y 
, удовлетворяющая условиям
)
(
...,
,
)
(
....,
,
)
(
,
)
(
1 1
0 0
n
n
i
i
y
x
F
y
x
F
y
x
F
y
x
F




Математическая постановка задачи интерполирования
Пусть на отрезке [x
0
, x
n
] задана функция y = f(x) своими n+1 значениями: y
0
= f(x
0
), y
1
= f(x
1
), …, y
n
= f(x
n
) в точках x
0
, x
1
,
…, x
n
, которые назовем узлами интерполяции. Предполагается, что при i ≠ j, x i
≠ x j
Требуется найти аналитическое выражение Y(x) функции, заданной таблично: x
0
x
1
… x
n y
0
y
1
… y
n которая в узлах интерполяции совпадает со значениями заданной функции, т.е. y
0
=Y(x
0
), y
1
=Y(x
1
), …, y
n
=Y(x
n
).
Процесс вычисления значений функции в точках x, отличных от узлов интерполяции, называют интерполированием функции f(x).
Если аргумент x, для которого определяется приближенное значение функции [x
0
, x
n
], то задача называется интерполированием в узком смысле.
Если x находится за пределами отрезка [x
0
, x
n
], то задача отыскания значения функции в точке x называется экстраполированием.
Геометрически задача интерполирования для функции одной переменой y = f(x) означает построение кривой, проходящей через точки плоскости с координатами (x
0
, y
0
), (x
1
, y
1
), …, (x
n
, y
n
)(рис. 3.1). следующие формулы для уточнения корня уравнения:

23
Рис. 3.1
Очевидно, что через данные точки можно провести бесконечно много кривых. Таким образом, задача отыскания функции Y(x) по конечному числу ее значений является неопределенной. Но если в качестве интерполирующей функции Y(x) взять многочлен степени не выше nY
n
(x), то задача станет однозначной.
Локальная и глобальная интерполяция
Если задан узел интерполяции, то на этих узлах можно построить один интерполяционный многочлен n-й степени, многочленов первой степени и большой набор многочленов степени меньше n, опирающиеся на некоторые из этих узлов.
Теоретически максимальную точность обеспечивает многочлен более высокой степени. Однако на практике наиболее часто используют многочлены невысоких степеней, во избежание погрешностей расчета коэффициентов при больших степенях многочлена.
Если функция интерполируется на отрезке с помощью единого многочлена для всего отрезка, то такую интерполяцию называют глобальной. В случае локальной интерполяции на каждом интервале строится отдельный интерполяционный полином невысокой степени.
Виды:
•
Алгебраическая интерполяция
•
Кусочно-линейная интерполяция
•
Сплайн-интерполяция
•
Тригонометрическая интерполяция
12.
Прямая и обратная интерполяции по Лагранжу. Достоинства и
недостатки. Алгоритмы
1.
Алгебраическая интерполяция

24
При алгебраической интерполяции интерполирующая функция может быть написана непосредственно по таблице значений в виде интерполяционного полинома
Лагранжа n -ой степени
)
)...(
)(
)....(
)(
(
)
)...(
)(
)....(
)(
(
)
(
1 1
1 0
1 1
1 0
0
n
i
i
i
i
i
i
i
n
i
i
n
i
i
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
y
x
Ln
y


















Узлы интерполяции при этом могут быть как равноотстоящими, так и неравноотстоящими. Представленный полином позволяет выполнять прямую интерполяцию. По таблице можно написать также полином Лагранжа для обратной интерполяции
)
)...(
)(
)....(
)(
(
)
)...(
)(
)....(
)(
(
)
(
0 1
1 1
0 1
1 1
0


















n
i
n
i
i
i
i
i
i
i
n
i
i
i
y
y
y
y
y
y
y
y
y
y
y
y
y
y
y
y
y
y
y
y
x
y
Ln
x
Для разработки алгоритмов полиномы удобнее представить в виде









n
i
j
j
j
i
j
n
i
i
x
x
x
x
y
x
Ln
y
0 0
,
)
(
)
(
0 0









n
i
j
j
j
i
j
n
i
i
y
y
y
y
x
y
Ln
x
Алгоритмы прямой и обратной интерполяции по Лагранжу одинаковы, просто засеняй х на у.

25
13.
Кусочно-линейная
интерполяция
и
экстраполяция.
Сплайн-
интерполяция. Достоинства и недостатки.
Рис.2.1 – алгоритм прямой интерполяции по Лагранжу
начало
x
n
i
y
x
n
i
i


,
)
1
(
0
,
,
,
x
x
x
x
x
x
n





;
;
0





i
n
i
l
i
;
1
;
0
,
0






j
n
j
y
p
j
i
;
1
,
,
0

i
j 
j
i
j
x
x
x
x
p



*
j
нет
p
l


i
l
x,
x
конец

26
При кусочно-линейной интерполяции вычисление дополнительных точек выполняется по линейной зависимости. Графически это означает соединение узловых точек отрезками прямых. При экстраполяции используются отрезки прямых, проведенных через две крайние точки.
При небольшом числе узлов (<10) кусочно-линейная интерполяция оказывается довольно грубой. При ней даже первая производная интерполирующей функции испытывает резкие скачки в узловых точках.
2.
Сплайн-интерполяция
Гораздо лучшие результаты, по сравнению с кусочно-линейной, дает сплайн- интерполяция (splinе – гибкая линейка). Здесь исходная функция заменяется отрезками кубических полиномов, проходящих через три смежные узловые точки.
Коэффициенты полиномов
3 2
2 1
3 0
a
x
a
x
a
x
a



, т.е.
3 2
1 0
,
,
,
a
a
a
a
, рассчитываются так, чтобы первая и вторая производные были непрерывными. Линия которую описывает сплайн-функция напоминает по форме гибкую линейку закрепленную в узловых точках
Кусочно-квадратичная интерполяция
В случае квадратичной интерполяции, для каждых трех узловых точек
,
,
, строится уравнение параболы:
, при
(3.8)
Рис.3.2. Кусочно-квадратичная интерполяция
Здесь коэффициенты
, и разные на каждом интервале и определяются решением системы уравнений для условия прохождения параболы через три точки:

27
(3.9)
Из системы уравнений (3.9) можно найти коэффициенты:
(3.10)
14.
Тригонометрическая интерполяция. Достоинства и недостатки.
Алгоритм.
Пусть функция
)
(x
f
задана на отрезке
]
2
,
0
[

таблицей значений
)
(
i
x
f
в равноотстоящих узлах
),
1 2
/(
2


n
i
x
i

2
,....,
1
,
0
n
i 
Тригонометрическим многочленом степени m называют многочлен
)
sin cos
(
2
)
(
1 0





m
k
k
k
m
kx
b
kx
a
a
x
P
Задача тригонометрической интерполяции состоит в построении тригонометрического интерполяционного многочлена наименьшей степени удовлетворяющего условиям
2
...,
,
1
,
0
),
(
)
(
n
i
x
f
x
P
i
i
m


Решением этой задачи является тригонометрический многочлен
,
)
sin cos
(
2
)
(
1 0





n
k
k
k
n
kx
b
kx
a
a
x
P
коэффициенты которого вычисляются по следующим формулам:

28 1
2 2
sin
)
(
1 2
1
,
1 2
2
cos
)
(
1 2
1
,
)
(
1 2
1 2
0 2
0 2
0 0














n
ki
x
f
n
b
n
ki
x
f
n
a
x
f
n
a
n
i
i
k
n
i
i
k
n
i
i


Широкие возможности тригонометрической интерполяции следуют из того факта что с возрастанием n многочлен
 
x
P
n
аппроксимирует
 
x
f
с возрастающей точностью Это справедливо для достаточно широкого класса функций Этим тригонометрическая интерполяция существенно отличается от алгебраической интерполяции на системе равноотстоящих узлов
При алгебраическом интерполировании разность между функцией
 
x
f
и интерполяционным многочленом может быть как угодно большой всюду кроме узлов интерполяции
Тригонометрическое интерполирование свободно от этого недостатка

29
15.
Методы аппроксимации – линейной и линейной общего вида.
Достоинства и недостатки.
Математическое уравнение, которое оценивает линию простой (парной) линейной регрессии:
Рис.2.4 – алгоритм тригонометрической интерполяции
начало
n
1
,
1
*
2


n
длиной
b
a
массивы
под
и
n
длиной
x
массив
под
памяти
выделение
0 0
0

 b
a




i
n
i
i
;
1 2
;
0

1 2
2


n
i
x
i

)
(
0
i
x
f
a


i
)
1 2
(
0 0


n
a
a
0 0
, b
a




k
n
k
k
;
;
1 0


k
k
b
a




i
n
i
i
;
1 2
;
0

)
sin(
*
)
(
)
cos(
*
)
(
i
i
k
i
i
k
kx
x
f
b
kx
x
f
a




i
)
1 2
(
/
)
1 2
(
/




n
b
n
a
k
k
k
k
b
a ,
k
графика
построение
и
x
P
значений
Вычисление
n
)
(
конец

30
Y=a+bx.
x называется независимой переменной или предиктором.
Y – зависимая переменная или переменная отклика. Это значение, которое мы ожидаем для y (в среднем), если мы знаем величину x, т.е. это «предсказанное значение y»
a – свободный член (пересечение) линии оценки; это значение Y, когда x=0 (Рис.1).
b – угловой коэффициент или градиент оценённой линии; она представляет собой величину, на которую Yувеличивается в среднем, если мы увеличиваем x на одну единицу.
a и b называют коэффициентами регрессии оценённой линии, хотя этот термин часто используют только для b.
Парную линейную регрессию можно расширить, включив в нее более одной независимой переменной; в этом случае она известна как множественная регрессия.