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

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

1
Оглавление
1.Основные характеристики численных методов. Взаимосвязь характеристик.
Причины появления ошибок численных методов. ............................................................ 4 2.Этапы решения нелинейных уравнений. Иллюстрация и алгоритм этапа отделения корней ................................................................................................................... 5 3.Иллюстрация и алгоритм метода деления пополам.
7 4.Иллюстрация и алгоритм метода хорд.
10 5..
Иллюстрация и алгоритм метода касательных.
12 6.Иллюстрация и алгоритм метода секущих.
14 7.Иллюстрация и алгоритм метода итераций.
16 8.Алгоритм комбинированного метода хорд и касательных.
18 9.Алгоритм комбинированного метода деления пополам и итераций.
20 10.Алгоритм расчета зависимости затрат машинного времени от задаваемой ошибки в методах уточнения корней нелинейных уравнений. ...................................... 21 11.Интерполяция и экстраполяция. Постановка задачи интерполяции. Методы интерполяции (перечислить) .............................................................................................. 21
Локальная и глобальная интерполяция ................................................................. 23 12.Прямая и обратная интерполяции по Лагранжу. Достоинства и недостатки.
Алгоритмы ............................................................................................................................ 23 13.Кусочно-линейная интерполяция и экстраполяция. Сплайн-интерполяция.
Достоинства и недостатки. ................................................................................................. 25
Кусочно-квадратичная интерполяция ................................................................... 26 14.Тригонометрическая интерполяция. Достоинства и недостатки. Алгоритм.
27 15.Методы аппроксимации – линейной и линейной общего вида. Достоинства и недостатки. ........................................................................................................................... 29

2 16.Задаваемая и фактическая ошибки при вычислении значения интеграла.
Зависимость фактической ошибки от шага интегрирования и задаваемой ошибки.
Затраты машинного времени. ............................................................................................. 31 17.Алгоритмы формирования матриц (верхней и нижней треугольных, неособенной и особенной). ................................................................................................. 33 18.Разложение неособенной матрицы в произведение треугольных матриц.
Алгоритм. Характеристики разложения. .......................................................................... 36 19.Методы обращения матриц.
Характеристики обращения.
39 20.Прямые методы решения СЛАУ. Алгоритм метода Гаусса с частичным выбором ведущего коэффициента по столбцу. Ошибки и затраты машинного времени.
41 21.Итерационные методы решения СЛАУ. Алгоритм метода Гаусса-Зейделя.
44 22.Сравнение прямых и итерационных методов решения СЛАУ. Рекомендации при вычислении матричных выражений. .......................................................................... 47 23.Постановка задачи аппроксимации
(регрессии).
Выбор критерия.
47 24.Метод аппроксимации алгебраическим полиномом. Алгоритм метода.
48 25.Формула Ньютона-Котеса для вычисления определенных интегралов. Частные случаи. ................................................................................................................................... 51 26.Формула Гаусса для вычисления определенных интегралов. Формулы прямоугольников – срединных, левых, правых. .............................................................. 54 27.Алгоритм получения зависимости от шага интегрирования фактической ошибки вычисления интеграла по формуле прямоугольников ...................................... 56 28.Алгоритм получения зависимости от шага интегрирования фактической ошибки вычисления интеграла по формуле Гаусса. ........................................................ 58
Алгоритмы для получения зависимости фактической ошибки вычисления интеграла от шага интегрирования ................................................................................ 59 29.Алгоритм получения зависимости от шага интегрирования фактической ошибки вычисления интеграла в частных случаях формулы Ньютона-Котеса. .......... 59 30.Алгоритм получения зависимости от шага интегрирования фактической ошибки вычисления интеграла по формуле Ньютона-Котеса. ....................................... 62

3
Алгоритмы для получения зависимостей фактической ошибки и временных затрат вычисления интеграла от задаваемой ошибки интегрирования .................... 63 31.Адаптивный алгоритм получения зависимостей от задаваемой ошибки затрат машинного времени и фактической ошибки вычисления интеграла по формуле прямоугольников. ................................................................................................................ 64 32.Адаптивный алгоритм получения зависимостей от задаваемой ошибки затрат машинного времени и фактической ошибки вычисления интеграла по формуле Гаусса.
66 33.Адаптивный алгоритм получения зависимостей от задаваемой ошибки затрат машинного времени и фактической ошибки вычисления интеграла в частных случаях формулы Ньютона-Котеса. ................................................................................................. 68 34.Адаптивный алгоритм получения зависимостей от задаваемой ошибки затрат машинного времени и фактической ошибки вычисления интеграла по формуле
Ньютона-Котеса. .................................................................................................................. 69 35.Численные методы интегрирования ОДУ и систем ОДУ (перечислить). Метод интегрирования ОДУ с помощью ряда Тейлора. ............................................................. 71 36.Метод Эйлера и модифицированные методы Эйлера интегрирования ОДУ.
Иллюстрации методов ......................................................................................................... 72 37.Методы Рунге-Кутта интегрирования ОДУ. Достоинства и недостатки методов. Пример алгоритма. .............................................................................................. 75 38.Интегрирование систем ОДУ и ОДУ высших порядков. Пример алгоритма.
76 39.Методы прогноза и коррекции (перечислить). Иллюстрация простого метода прогноза и коррекции. ......................................................................................................... 78 40.Оценки ошибок ограничения в методе прогноза и коррекции. Уточнение решения................................................................................................................................. 80 41.Достоинства и недостатки методов прогноза и коррекции. Интегрирование
ОДУ и систем ОДУ в Matchad’е. ....................................................................................... 81 42.Пример алгоритма интегрирования ОДУ методом прогноза и коррекции.
82 43.Адаптивный алгоритм интегрирования ОДУ методом прогноза и коррекции.
86 44.Методы
Рунге-Кутта интегрирования
ОДУ.
Пример алгоритма.
88

4
1.
Основные
характеристики
численных
методов.
Взаимосвязь
характеристик. Причины появления ошибок численных методов.
Все численные методы обладают некоторым набором характеристик. Наиболее важной из них является точность. На всех этапах решения задачи могут возникать погрешности, искажающие результаты вычислений, которые и определяют точность.
При анализе точности одним из важнейших критериев является сходимость численного метода. Для дискретных методов (методы, которые заключаются в замене задачи с непрерывными функциями на задачу, в которой значения функций заданы в фиксированных точках) сходимость – это стремление значений решения метода к соответствующим значениям решения исходной задачи при стремлении к нулю параметра дискретизации (например, шага интегрирования).
Задача называется поставленной корректно, если для любых значений исходных данных из некоторого класса ее решение существует, единственно и устойчиво.
Применять для решения некорректно поставленных задач численные методы, не имеет смысла, поскольку возникающие в расчетах погрешности округления будут сильно возрастать в ходе вычислений, что приведет к значительному искажению результатов.
Устойчивость – это чувствительность метода к неточностям в исходных данных.
Задача называется устойчивой, если малые погрешности в исходной величине приводят к малым погрешностям в решении. Отсутствие устойчивости означает, что даже незначительные погрешности в исходных данных приводят к большим погрешностям в решении или даже к неверному результату. О неустойчивых задачах также говорят, что они чувствительны к погрешностям исходных данных.
Таким образом, для получения решения задачи с необходимой точностью ее постановка должна быть корректной, а используемый численный метод должен обладать устойчивостью (корректностью) и сходимостью.
В большинстве случаев, кроме точности (сходимости, устойчивости, корректности) необходимо следить за минимизацией трудоемкости решения.
Применительно к вычислительным задачам трудоемкость определяется объёмом памяти, используемым в процессе поиска решения, и временем, необходимым для выполнения вычислений. Время обычно измеряется в количестве элементарных

5 операций (сложения, умножения, и т.д.), которые необходимо выполнить для решения задачи. Эти характеристики желательно уменьшать построением оптимальных алгоритмов вычисления, не потеряв при этом в точности. К сожалению, часто уменьшение трудоемкости и увеличение точности являются взаимоисключающими параметрами, и главной задачей является найти баланс между ними.
Источники погрешностей
Математическая модель задачи является неточной
Погрешность возникает из-за того, что сам численный метод или математическая модель является лишь приближением к точному методу
(например, дифференцирование). Кроме того, любая математическая модель или метод могут внести существенные погрешности, если в ней не учтены какие-то особенности рассматриваемой задачи. Модель может прекрасно работать в одних условиях и быть совершенно неприемлемой в других. Такую погрешность называют также методической. Она всегда имеет место, даже при абсолютно точных данных и абсолютно точных вычислениях. В большинстве случаев погрешность численного метода можно уменьшить до требуемого значения за счет изменения параметров метода (например, уменьшением шага дискретизации, или увеличением количества итераций).
Ошибки в исходных данных
Исходные данные задачи часто являются основным источником погрешностей.
Ошибки такого типа неизбежны и проявляются в любых реальных задачах, поскольку любое измерение может быть проведено с только какой-то предельной точностью.
Вместе с погрешностями, вносимыми математической моделью, их называют неустранимыми погрешностями, поскольку они не могут быть уменьшены ни до начала решения задачи, ни в процессе ее решения.
Следует стремиться к тому, чтобы все исходные данные были примерно одинаковой точности. Сильное уточнение одних исходных данных при наличии больших погрешностей в других не приводит к повышению точности конечных результатов. Если какие-то отдельные точки данных (измерения) явно ошибочные, их можно исключить из вычислений.
Вычислительные ошибки (ошибки округления)
Ошибки этого типа проявляются из-за дискретной (а не непрерывной) формы представления величин в компьютере. Вычислительные ошибки можно свести к минимуму продуманно организовывая алгоритмы. (Представление чисел с плавающей точкой, Погрешность округления)
2.
Этапы решения нелинейных уравнений. Иллюстрация и алгоритм этапа
отделения корней

6
Процесс вычисления корней нелинейных уравнений состоит из двух этапов:
1) отделение корней, т.е. установление возможно более тесных промежутков
 
b
a,
, в которых содержится один и только один корень уравнения
;
0
)
(

x
f
2) уточнение отделенных корней, т.е. доведение значений корней до заданной степени точности.
Отделение корней
Для отделения корней можно воспользоваться методом линейного поиска, в котором диапазон поиска


в
н
x
x ,
проходится с шагом
;
a
b
x



при выполнении условия
0
)
(
*
)
(


 x
x
f
x
f
принимается решение о наличии корня в промежутке
 
b
a,
. В общем случае в диапазоне поиска может оказаться несколько корней (
1

m
), к каждому из которых следует применить операцию уточнения. Иллюстрация и алгоритм отделения корней представлены соответственно на рис.1.1 и 1.2
Рис.1.1 – иллюстрация к отделению корней
x
y
x

x

x

н
x
в
x
a
b
1

m
0

m
'
a
'
b
2

m
)
(x
f
y 
)
(a
f
)
(b
f
)
(
0
н
x
f
y 
)
(
1
x
x
f
y
н




7
3.
Иллюстрация и алгоритм метода деления пополам.
Метод деления пополам (метод дихотомии, метод бисекций)
Это наиболее надежный алгоритм, особенно когда о поведении
)
(x
f
известно только, что
)
(x
f
- функция действительной переменной x и известен интервал
 
b
a,
, на котором
)
(x
f
меняет знак (рис.1.3). Следовательно, между
a и b существует точка, в которой функция обращается в нуль. Если разделить интервал пополам и узнать, больше нуля или меньше нуля функция в точке деления, то можем указать
Рис.1.2 – алгоритм отделения корней
начало
x
x
x
в
н

,
,
0
),
(
0
,



m
x
f
y
x
x
н
x
x



в
x
x 
"
"корней
m
конец
)
(
1
x
f
y 
0 1
*
0

y
y
нет
x
b
a
x
b
m






,
,
b
a
m
,
,
1 0
y
y 
нет

8 подынтервал, в котором функция меняет знак. Последующим делением указываемых подынтервалов можно сколь угодно близко подойти к корню: например, за 10 шагов интервал с корнем будет уменьшен в 1024 раза. При заданной абсолютной точности

алгоритм метода деления пополам состоит из следующих шагов (рис.1.4)
1.
Вычислить
)
(
0
a
f
y 
и
)
2
/
)
((
1
b
a
f
y


. Затраты машинного времени на уточнение корня оценивают косвенно, по количеству обращений к функции
)
(x
f
- n , следовательно, n будет инкрементирован дважды.
2.
Если знаки
0
y
и
1
y
не совпадают, т.е.
0 1
*
0

y
y
, и




2
/
)
(
b
a
a
,то нужно заменить b на
2
/
)
(
b
a 
и перейти к п.1.
3.
Если же при


2
/
)
(
0 1
*
0
b
a
a
y
y



, следует прекратить вычисления, т.к. достигнута заданная точность.
4.
Если
0 1
*
0

y
y
, и




2
/
)
(
b
a
b
, то нужно заменить a на
2
/
)
(
b
a 
и перейти к п.1; в противном случае - прекратить вычисления, так как достигнута заданная точность. Любой из концов отрезка
 
b
a,
, а лучше его середина может быть использована в качестве корня
*
x уравнения
0
)
(

x
f
.
Отметим основные достоинства метода деления пополам: 1) абсолютно надежен;
2) скорость сходимости не зависит от вида
)
(x
f
.

9
Рис.1.3а,б – иллюстрации к методу деления пополам
a
b
x
0
y
1
y
)
(x
f
2
b
a 
y
b
границы
перенос
б)
*
x
a
b
x
0
y
1
y
)
(x
f
2
b
a 
y
a
границы
перенос
а)
*
x

10
4.
Иллюстрация и алгоритм метода хорд.
Метод хорд
Метод деления пополам будет улучшен, если для следующего вычисления использовать не середину отрезка
 
b
a,
, а то значение ,
x в котором дает нуль линейная интерполяция между двумя известными значениями функции
)
(x
f
противоположного знака (рис.1.5).
Геометрически способ линейной интерполяции эквивалентен замене кривой
)
(x
f
y 
хордой, проходящей через точки
))
(
,
(
a
f
a
A
и
)).
(
,
(
b
f
b
B
Уравнение хорды:
)).
(
)
(
/(
))
(
0
(
)
/(
)
0
(
a
f
b
f
a
f
y
a
b
a
x





Полагая
0 0 
y
и
,
0
c
x 
получаем приближение к корню:
))
(
)
(
/(
)
(
*
)
(
a
f
b
f
a
b
a
f
a
c




 (1)
Рис.1.4 – алгоритм метода деления пополам
начало

,
, b
a
0

n




n
x
f
y
a
x
),
(
0
,





n
x
f
y
b
a
x
),
(
1
,
2
/
)
(
0 1
*
0

y
y


a
x 


b
x 
n
y
x
,
1
,
,

x
b 
x
a 
конец
да
да
да

11
Алгоритм метода хорд (рис.1.6):