Линейная алгебра и мат. Статистика
Метод сопряжённых градиентов
жүктеу/скачать 294.26 Kb.
|
- Бұл бет үшін навигация:
- Предобуславливание
| Метод сопряжённых градиентов — итерационный метод для безусловной оптимизации в многомерном пространстве. Основным достоинством метода является то, что он решает квадратичную задачу оптимизации за конечное число шагов.
Данный метод является точным. Его суть заключается в том, чтобы выбирать параметры таким образом, чтобы каждый следующий вектор невязки был ортогонален всем предыдущим. Так как мы рассматриваем конечномерные пространства, то на последнем шаге вектор невязки будет нулевым, так как в конечномерном пространстве число ненулевых взаимно ортогональных векторов конечно. Таким образом можно получить точное решение за конечное число итераций. Предобуславливание (также предобусловливание) — процесс преобразования условий задачи для её более корректного численного решения. Предобуславливание обычно связано с уменьшением числа обусловленности задачи. Предобуславливаемая задача обычно затем решается итерационным методом. Предобуславливание используется в итерационных методах при решении систем линейных алгебраических уравнений вида , так как скорость сходимости для большинства итерационных линейных решателей увеличивается с уменьшением числа обусловленности в результате предобуславливания. Решатели с предобуславливанием обычно эффективнее, чем использование простых решателей, например, таких как метод Гаусса в случае больших и особенно в случае разреженных матриц. Итерационные решатели с предобуславливанием могут использовать безматричные методы, в которых матрица коэффициентов не хранится отдельно, а доступ к её элементам происходит через произведения матриц-векторов. Задача о рюкзаке, варианты, методы решения. Теорема об алгоритмах с гарантированной абсолютной точностью. Жадные алгоритмы. Пусть есть разных предметов, каждый предмет имеет вес и полезность , так же имеется максимальный вес , который можно положить в рюкзак. Требуется собрать такой набор предметов , чтобы полезность их была наибольшей, а суммарный вес не превышал . Задача о загрузке (задача о рюкзаке) и различные её модификации широко применяются на практике в прикладной математике, криптографии, экономике, логистике, для нахождения решения оптимальной загрузки различных транспортных средств: самолетов, кораблей, железнодорожных вагонов и т.д. Существует несколько модификаций задачи: Каждый предмет можно брать только один раз. Каждый предмет можно брать сколько угодно раз. Каждый предмет можно брать определенное количество раз На размер рюкзака имеется несколько ограничений. Некоторые вещи имею больший приоритет, чем другие жүктеу/скачать 294.26 Kb. Достарыңызбен бөлісу:
|