Критерий окончания итераций

Минимизирующая последовательность

то есть, последовательности приближений к экстремуму, каждое следующее значение используется для нахождения следующего

Критерий окончания итераций

4. Геометрическая интерпретация метода поиска минимума. Теорема о сходимости методов первого порядка.

От 5-8 геом. интерпретации

 

 

 

5. Метод градиентного спуска.

 

 

 

 

6. Метод наискорейшего спуска. Способы адаптивного вычисления шага спуска.

ПРИМЕР 2.

 

 

7. Метод покоординатного спуска. Метод наискорейшего покоординатного спуска (Гаусса-Зейделя).

 

 

8. Метод сопряженных градиентов (Флетчера-Ривса).

 

9. Метод Ньютона. Численная реализация метода. Критерии сходимости.

ПРИМЕР

 

 

10. Задача поиска экстремальных значений функционала с ограничениями типа «равенства».

 

11. Метод исключений для сведения задачи к поиску безусловного экстремума.

 

 

12. Метод множителей Лагранжа.

13. Метод штрафной функции.

 

 

14. Формулировка канонической и основной задач линейного программирования. Алгоритм графического решения на плоскости для случая функции двух переменных.

 

 

15. Алгоритм табличного симплекс-метода (метод Данцига). Разрешающая строка и коэффициенты пересчета таблицы.

 

 

 

16. Отделение и уточнение корней. Метод дихотомии (половинного деления) для уточнения корней.

 

17. Метод касательных (Ньютона) решения алгебраических уравнений.

УСЛОВИЯ СХОДИМОСТИ

АЛГОРИТМ МЕТОДА НЬЮТОНА

Пример 3

 

18. Метод простых итераций. Условия сходимости. Программная реализация метода простых итераций.

19. Интерполяционный полином Лагранжа. Первая интерполяционная формула. Программная реализация на языке JavaScript.

 

 

20. Рациональные кривые Безье. Алгоритм (программа на Action Script 3).

 

 

 

Кривая Безье является частным случаем многочленов Бернштейна, представляет собой параметрическую кривую и задаётся выражением:

, где

n — количество опорных точек;
i — номер опорной точки;
t — шаг на котором мы считаем положение кривой. К примеру, при построении кривой по 100 точкам, шаг будет 0,01 (не опорным, а точкам на самой кривой);
Р — в нашем случае координата опорной точки;
b(t) — базисная функция кривой Безье. Этот коэффициент, определяет вес опорной точки. Является собственно полином Бернштейна:

, где — число сочетаний из n по i, где n — степень полинома, i — порядковый номер опорной вершины.

На первом и последнем шагах значение полинома Бернштейна равно 1, объяснение здесь. На середину кривой наибольшее влияние оказывают средние опорные точки, в первой трети — опорные точки первой трети и так далее. Полином Бернштейна принимает значения от 0 до 1.

И так, чтобы посчитать координату кривой Безье нам надо:

 

1. Посчитать вес опорной точки;

2. Умножить вес на координату этой опорной точки;

3. Повторить шаги 1-2 для всех опорных точек;

4. Сложить получившиеся значения — это и будет координата кривой.

5. Считаем базисную функцию:

6. // i - номер вершины, n - количество вершин, t - положение кривой (от 0 до 1)

7. function getBezierBasis(i, n, t) {

8. // Факториал

9. function f(n) {

10.  return (n <= 1)? 1: n * f(n - 1);

11. };

12. 

13. // считаем i-й элемент полинома Берштейна

14.return (f(n)/(f(i)*f(n - i)))* Math.pow(t, i)*Math.pow(1 - t, n - i);

15.}

 

 

21. Интерполяция кардинальными сплайнами.

· Сплайн -функция, область определения которой разбита на конечное число отрезков, на каждом из которых она совпадает с некоторым алгебраическим многочленом (полиномом). Максимальная из степеней использованных полиномов называется степенью сплайна. Разность между степенью сплайна и получившейся гладкостью называется дефектом сплайна.

· сплайны — это решения многоточечных краевых задач сеточными методами.

Другими словами сплайн — это кусочно заданная функция, то есть совокупность нескольких функций, каждая из которых задана на каком-то множестве значений аргумента, причем эти множества попарно непересекающиеся.

 

22. Интерполяция по формуле Ньютона.

 

23. Шейдерный язык AGAL (Adobegraphicsassemblylanguage) и отображение графики с помощью технологии Stage3D.

24. Текстурное представление матриц данных в памяти GPU. Параллельное решение двумерной нестационарной задачи Дирихле на GPU.

25. Парадигма ILP (Instructionlevelparallelism) для оптимизации времени выполнения графических шейдеров

 

26. Численная линейная интерполяция на MATLAB.

Интерполяция

Интерполяция (интерполирование) — процесс нахождения промежуточных значений по ряду данных, для восполнения пробелов между точными значениями приближенными. Точные значения так же называют узловыми точками.