- •1. Внутренняя сортировка данных методом подсчета. Эффективность данного алгоритма. Привести фрагмент программы, поясняющий данный алгоритм.
- •2. Внутренняя сортировка данных методом выбора. Эффективность данного алгоритма. Привести фрагмент программы, поясняющий данный алгоритм.
- •3. Внутренняя сортировка данных методом простых вставок. Эффективность данного алгоритма. Привести фрагмент программы, поясняющий данный алгоритм.
- •4. Внутренняя сортировка данных методом Шелла. Эффективность данного алгоритма. Привести фрагмент программы, поясняющий данный алгоритм.
- •5. Внутренняя сортировка данных методом «пузырька». Эффективность данного алгоритма. Привести фрагмент программы, поясняющий данный алгоритм.
- •6. Внутренняя сортировка данных «быстрым» методом. Эффективность данного алгоритма. Привести фрагмент программы, поясняющий данный алгоритм.
- •7. Численное решение уравнения методом половинного деления (дихотомии). Эффективность данного алгоритма. Привести фрагмент программы, поясняющий данный алгоритм.
- •Метод хорд
- •9. Численное решение уравнения методом Ньютона (касательных). Эффективность данного алгоритма. Привести фрагмент программы, поясняющий данный алгоритм.
- •10. Численное решение уравнения модифицированным методом Ньютона. Эффективность данного алгоритма. Привести фрагмент программы, поясняющий данный алгоритм. Модифицированный метод Ньютона
- •Модифицированный метод Ньютона (метод секущих)
- •Метод ньютона-рафсона
- •11. Численное решение уравнения методом секущих. Эффективность данного алгоритма. Привести фрагмент программы, поясняющий данный алгоритм.
- •Условие сходимости
- •12. Численное решение уравнения методом простых итераций. Эффективность данного алгоритма. Привести фрагмент программы, поясняющий данный алгоритм. Метод простых итераций
- •13. Численное интегрирование методом прямоугольников. Эффективность данного алгоритма. Привести фрагмент программы, поясняющий данный алгоритм. Метод прямоугольников
- •Пример реализации
- •14. Численное интегрирование методом трапеций. Эффективность данного алгоритма. Привести фрагмент программы, поясняющий данный алгоритм. Метод трапеций
- •Составная формула
- •Формула
- •Представление в виде метода Рунге-Кутта
- •Составная формула (формула Котеса)
- •16. Численное интегрирование методом Гаусса-Лежандра. Эффективность данного алгоритма. Привести фрагмент программы, поясняющий данный алгоритм.
- •17. Численное интегрирование методом Монте-Карло. Эффективность данного алгоритма. Привести фрагмент программы, поясняющий данный алгоритм. Интегрирование методом Монте-Карло
- •Обычный алгоритм Монте-Карло интегрирования
- •Геометрический алгоритм Монте-Карло интегрирования
- •Использование выборки по значимости
- •Применения
- •Случай равномерного распределения узлов интерполяции
- •Интерполяция полиномами Лагранжа и Ньютона
- •Погрешность интерполирования
- •Выбор узлов интерполяции
- •Изложение метода
- •Метод прогонки
- •Пример: интерполирование неизвестной функции
- •Ошибка интерполяции
- •Пример: интерполяция синуса
- •Дискретное преобразование Фурье
- •Пример использования
- •Погрешность вычислений
- •Программная реализация
Модифицированный метод Ньютона (метод секущих)
В этом методе для вычисления производных на каждом шаге поиска используется численное дифференцирование по формуле:
Тогда рекуррентная формула (4.6) будет иметь вид:
(4.10) |
где
Метод ньютона-рафсона
Повышение эффективности метода за счёт использования информации о производной накладывает дополнительные ограничения на функцию. Кроме унимодальности функция должна быть непрерывной и дважды дифференцируемой.
2.5.1. Метод Ньютона-Рафсона.
Пусть - непрерывная и дважды дифференцируемая функция.
Требуется найти корень уравнения .
Зададим – начальную точку поиска. Построим линейную аппроксимацию функции в точке . Для этого разложим в ряд Тейлора в точке и отбросим все члены второго порядка и выше.
Сходимость метода зависит от выбора начальной точки и вида функции.
не сходится
Условие выхода
11. Численное решение уравнения методом секущих. Эффективность данного алгоритма. Привести фрагмент программы, поясняющий данный алгоритм.
Метод секущих — один из численных методов решения уравнений.
В качестве функции берут любую постоянную , знак которой совпадает со знаком производной в окрестности (и, в частности, на отрезке, соединяющем и ). Постоянная не зависит также и от номера шага. Тогда формула итераций оказывается очень проста:
и на каждой итерации нужно один раз вычислить значение функции .
Выясним смысл этой формулы, а также смысл условия о совпадении знаков и . Рассмотрим прямую, проходящую через точку на графике с угловым коэффициентом . Тогда уравнением этой прямой будет
Иллюстрация последовательных приближений метода секущих.
Найдём точку пересечения этой прямой с осью из уравнения
откуда . Следовательно, эта прямая пересекает ось как раз в точке следующего приближения. Тем самым получаем следующую геометрическую интерпретацию последовательных приближений. Начиная с точки , через соответствующие точки графика проводятся секущие с угловым коэффициентом того же знака, что производная . (Заметим, что, во-первых, значение производной вычислять не обязательно, достаточно лишь знать, убывает функция или возрастает; во-вторых, что прямые, проводимые при разных , имеют один и тот же угловой коэффициент и, следовательно, параллельны друг другу.) В качестве следующего приближения к корню берётся точка пересечения построенной прямой с осью .
На чертеже справа изображены итерации при в случае и в случае . Мы видим, что в первом случае меняющаяся точка уже на первом шаге «перепрыгивает» по другую сторону от корня , и итерации начинают приближаться к корню с другой стороны. Во втором случае последовательные точки приближаются к корню, оставаясь всё время с одной стороны от него.
Условие сходимости
Достаточное условие сходимости, таково:
Это неравенство может быть переписано в виде
откуда получаем, что сходимость гарантируется, когда, во-первых,
так как (тем самым проясняется смысл выбора знака числа ), а во-вторых, когда при всех на всём рассматриваемом отрезке, окружающем корень. Это второе неравенство заведомо выполнено, если
где . Таким образом, угловой коэффициент не должен быть слишком мал по абсолютной величине: при малом угловом коэффициенте уже на первом шаге точка может выскочить из рассматриваемой окрестности корня , и сходимости итераций к корню может не быть.