СОПРЯЖЕННЫХ ГРАДИЕНТОВ МЕТОД

СОПРЯЖЕННЫХ ГРАДИЕНТОВ МЕТОД

метод решения системы линейных алгебраич. уравнений Ах=b с положительно определенной матрицей А. Это прямой и итерационный метод одновременно: при любом начальном приближении он сходится за конечное число итераций, давая точное решение. В С. г. м. матрица системы не меняется в процессе вычислений, на каждой итерации она используется лишь для умножения на вектор. Поэтому порядок систем, решаемых на ЭВМ, может быть высоким, он определяется объемом числовой информации, задающей матрицу.
Структура С. г. м. как прямого метода основана на процессе последовательной A-ортогонализации системы векторов, представляющем собой обычный процесс ор-тогонализации (см. Ортогонализации метод )относительно скалярного произведения ( х, у) Т Ау. Если {s1, s2,. . ., sn} есть A-ортогональный оазис пространства, то точное решение х* системы при любом начальном приближении х 0 может быть получено из разложения

где r0=b-Ах0 -невязка х 0. ВС. г. м. A-ортогональные векторы s1, s2,. . ., sn строятся процессом A-ортогонализации невязок r0, r1,. . ., rn_1 последовательности приближений х 0, x1,. . ., xn-1, вычисляемых по формулам

Построенные таким образом векторы r0, rl,. . .,rn_1 и s1, s2,. . ., sn обладают следующими свойствами:

Расчетные формулы С. г. м. даются следующими рекуррентными соотношениями (см. [1]):

Процесс заканчивается при нек-ром для к-рого rk=0. При этом x*=xk. Момент обрыва процесса определен начальным приближением х 0. Из рекуррентных соотношений (2) следует, что векторы r0, rl,. . ., ri являются линейными комбинациями векторов r0, Аr0,...,А ir0. Так как векторы r0, rl,. . ., ri ортогональны, то обращение в нуль ri возможно лишь тогда, когда векторы r0, Аr0,. . ., А ir0 линейно зависимы, напр. когда в разложении r0 по базису из собственных векторов Атолько iкомпонент отличны от нуля. Этим соображением можно руководствоваться при выборе начального приближения.
С. г. м. относится к классу методов, в к-рых за решение принимается вектор, минимизирующий нек-рый функционал. Для вычисления этого вектора строится итерационная последовательность, сходящаяся к точке минимума. Последовательность х 0, х1,. . ., х n в (2) осуществляет минимизацию функционала f(x)=(Ax, х)-2(b, х). На 1-м шаге процесса (2) вектор si совпадает с направлением скорейшего спуска (градиентом) для поверхности f(x)=c в ( п-i )-мерном эллипсоиде, представляющем собой сечение поверхности плоскостью, сопряженной направлениям s1, s2,. . ., si-1.
Описанный процесс С. г. м. или близкие к нему имеют много различных названий: метод Ланцоша, метод Хестенса, метод Штифеля и т. д. Из всех методов, осуществляющих минимизацию функционала, С. г. м. является наилучшим в стратегич. плане: он дает максимальную минимизацию за га шагов. Однако вычисления (2) в реальных условиях машинной арифметики чувствительны к ошибкам округления, и условия (1) могут быть нарушены. Это препятствует окончанию процесса за n шагов. Поэтому С. г. м. продолжают за питераций, рассматривая его как бесконечный итерационный процесс минимизации функционала. Известны модификации схемы вычислений (2), более устойчивые к ошибкам округления (см. [3], [4]).

Лит.:[1] Фаддеeв Д. К., Фaддеева В. Н., Вычислительные методы линейной алгебры, М., 1983; [2] Березин И. С., Жидкoв Н. П., Методы вычислений, т. 2, М., 1960; [3] Воеводин В. В., Численные методы алгебры, М., 1966; [4] Бахвалов Н. С., Численные методы, М., 1974.
Г. Д. Ким.


Математическая энциклопедия. — М.: Советская энциклопедия. . 1977—1985.

Игры ⚽ Поможем написать реферат

Полезное


Смотреть что такое "СОПРЯЖЕННЫХ ГРАДИЕНТОВ МЕТОД" в других словарях:

  • Метод сопряженных градиентов — метод нахождения локального минимума функции на основе информации о её значениях и её градиенте. В случае квадратичной функции в минимум находится за n шагов. Содержание 1 Основные понятия 2 Обосновани …   Википедия

  • Метод сопряжённых градиентов — Метод сопряженных градиентов метод нахождения локального минимума функции на основе информации о её значениях и её градиенте. В случае квадратичной функции в минимум находится за шагов. Содержание 1 Основные понятия …   Википедия

  • Метод сопряжённых направлений — Метод сопряженных градиентов метод нахождения локального минимума функции на основе информации о её значениях и её градиенте. В случае квадратичной функции в минимум находится за n шагов. Содержание 1 Основные понятия 2 Обосновани …   Википедия

  • Метод покоординатного спуска — Содержание 1 Постановка задачи решения системы уравнений в терминах методов оптимизации 2 Градиентные методы …   Википедия

  • ТЯЖЕЛОГО ШАРИКА МЕТОД — метод решения задачи минимизации дифференцируемой функции f(x)на евклидовом пространстве Е п. Метод основан на рассмотрении системы дифференциальных уравнений к рая описывает движение материальной точки по поверхности y=f(x)в поле тяжести,… …   Математическая энциклопедия

  • ЧЕБЫШЕВСКИЙ ИТЕРАЦИОННЫЙ МЕТОД — итерационный алгоритм нахождения решения линейного уравнения учитывающий информацию о принадлежности Sр(A) спектра оператора А нек рому множеству и использующий свойства и параметры многочленов, наименее отклоняющихся от нуля на множестве и… …   Математическая энциклопедия

  • МАКСИМИЗАЦИЯ И МИНИМИЗАЦИЯ ФУНКЦИЙ — конечного числа переменных задача поиска экстремума функции под этой задачей понимается: 1) нахождение 2) отыскание точек максимума или минимума, если достигаются на допустимом множестве (см. Максимум и минимум функции). 3) построение… …   Математическая энциклопедия

  • ИТЕРАЦИОННЫЙ АЛГОРИТМ — рекурсивный алгоритм, реализующий в нек ром топологич. пространстве Vпоследовательность точечно множественных отображений Ak: V > V, при помощи к рых по начальной точке вычисляют последовательность точек согласно формулам Операцию (1) наз.… …   Математическая энциклопедия

  • Система уравнений и экстремальные задачи. Градиентные методы. — Система уравнений и экстремальные задачи. Градиентные методы. Содержание 1 Постановка задачи решения системы уравнений в терминах методов оптимизации …   Википедия

  • Градиентные методы — численные методы решения с помощью градиента задач, сводящихся к нахождению экстремумов функции. Содержание 1 Постановка задачи решения системы уравнений в терминах методов о …   Википедия


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»