Минимизация квадратичных функций. Градиентный метод наискорейшего спуска для отыскания минимума квадратичной функции f(x)=1\2+

Минимизация квадратичных функций.

Задание №1

1.  Изложить градиентный метод наискорейшего спуска (ГМНС) для отыскания минимума квадратичной функции ([1, 45-48], [2, 269-262]):

f(x)=1\2<Ax,x>+<b,x>,                      (1)

где – симметричная положительно определенная матрица. Указать скорость его сходимости и связь с решением системы уравнений Ах+b=0.

2.  Реализовать ГМНС на компьютере. В качестве критерия прекращения спуска предусмотреть любой из трех следующих:

Продемонстрировать работу программы для

Выходные данные программы:  - номер последнего шага. Решить систему и сравнить  с . Проверить вычисления при различных начальных векторах  и проследить за зависимостью k от .

Литература.

1.  Моисеев Н. Н., Иванилов Ю.П., Сталярова Е. М. Методы оптимизации, М. 1978

2.  Васильев Ф. П.  Численные методы решения экстремальных задач, М. 1988

3.  Пшеничный Б.Н., Данилин  Ю. М. Численные методы в экстремальных задачах, М. 1975

4.  Карманов В. Г. Математическое программирование, М., 1986 (176-180, 203-205) и М.1980 (170—174? 195-197)

5.  Фаддеев Д.К., Фаддеева В.Н. Вычислительные методы линейной алгебры, М.1960

Минимизация квадратичных функций.

Задание №2

1.  Изложить градиентный метод с дроблением шага (ГМДШ) для отыскания минимума квадратичной функции ([1, 42-44], [3, 51-55]):

                                                                f(x)=1\2<Ax,x>+<b,x>,                      (1)

где – симметричная положительно определенная матрица, <*,*> - скалярное произведение в Rⁿ. Указать скорость его сходимости и связь с решением системы уравнений Ах+b=0.

2.  Реализовать ГМДШ на компьютере. В качестве критерия прекращения спуска предусмотреть                         любой из трех следующих:

Продемонстрировать работу программы для

Выходные данные программы:  - номер последнего шага, входные данные: n, A, b, e, . Решить систему и сравнить  с . Проверить вычисления при различных начальных векторах  и проследить за зависимостью k от .

Литература.

1.  Моисеев Н. Н., Иванилов Ю.П., Сталярова Е. М. Методы оптимизации, М. 1978

2.  Васильев Ф. П.  Численные методы решения экстремальных задач, М. 1988

3.  Пшеничный Б.Н., Данилин  Ю. М. Численные методы в экстремальных задачах, М. 1975

4.  Карманов В. Г. Математическое программирование, М., 1986 (176-180, 203-205) и М.1980 (170—174, 195-197)

5.  Фаддеев Д.К., Фаддеева В.Н. Вычислительные методы линейной алгебры, М.1960

Минимизация квадратичных функций.

Задание №3

1.  Изложить метод покоординатного спуска с дроблением шага (МПСДШ) для отыскания минимума квадратичной функции ([2, 342-347], [4, 203-205, 176-180, 1986], [4, 170-174, 195-197, 1980]):

                                                                f(x)=1\2<Ax,x>+<b,x>,                      (1)

где – симметричная положительно определенная матрица, <*,*> - скалярное произведение в Rⁿ. Какова его связь с решением системы уравнений Ах+b=0? Сходится ли метод?

2.  Реализовать МПСДШ на компьютере. В качестве критерия прекращения спуска предусмотреть                         любой из следующих:

Продемонстрировать работу программы для

Выходные данные программы:  - номер последнего шага, входные данные: n, A, b, e, . Решить систему и сравнить  с . Проверить вычисления при различных начальных векторах  и проследить за зависимостью k от .

Литература.

1. Моисеев Н. Н., Иванилов Ю.П., Сталярова Е. М. Методы оптимизации, М. 1978

2.  Васильев Ф. П.  Численные методы решения экстремальных задач, М. 1988

3.  Пшеничный Б.Н., Данилин  Ю. М. Численные методы в экстремальных задачах, М. 1975

4.  Карманов В. Г. Математическое программирование, М., 1986 (176-180, 203-205) и М.1980 (170—174, 195-197)

5.  Фаддеев Д.К., Фаддеева В.Н. Вычислительные методы линейной алгебры, М.1960

Минимизация квадратичных функций.

Задание №4

1.  Изложить метод покоординатного спуска с одномерной минимизацией (МПСОМ) для отыскания точки минимума квадратичной функции ([2, 346-347], [1, 53-55]):

                                                                f(x)=1\2<Ax,x>+<b,x>,                      (1)

где – симметричная положительно определенная матрица, <*,*> - скалярное произведение в Rⁿ. Какова его связь с решением системы уравнений Ах+b=0? Сходится ли метод?

2.  Реализовать МПСОМ на компьютере. В качестве критерия прекращения спуска предусмотреть                         любой из двух следующих:

Продемонстрировать работу программы для