Методы решения систем нелинейных уравнений
Информация - Математика и статистика
Другие материалы по предмету Математика и статистика
?у Якоби F'(х) вычислить и обратить лишь один раз - в начальной точке , то от метода Ньютона (3.1.2) придем к модифицированному методу Ньютона
(3.2.1)
Этот метод требует значительно меньших вычислительных затрат на один итерационный шаг, но итераций при этом может потребоваться значительно больше для достижения заданной точности по сравнению с основным методом Ньютона (3.1.2), поскольку, являясь частным случаем МПИ (), он имеет лишь скорость сходимости геометрической прогрессии.
Компромиссный вариант - это вычисление и обращение матриц Якоби не на каждом итерационном шаге, а через несколько шагов (иногда такие методы называют рекурсивными).
Например, простое чередование основного (3.1.2) и модифицированного (3.2.1) методов Ньютона приводит к итерационной формуле
(3.2.2)
где k = 0,1,2,… За здесь принимается результат последовательного применения одного шага основного, а затем одного шага модифицированного метода, т.е. двухступенчатого процесса
(3.2.3)
Доказано, что такой процесс при определенных условиях порождает кубически сходящуюся последовательность ().
3.3 Метод Ньютона с последовательной аппроксимацией матриц
Задачу обращения матриц Якоби на каждом k-м шаге метода Ньютона (3.1.2) можно попытаться решать не точно, а приближенно. Для этого можно применить, например, итерационный процесс Шульца, ограничиваясь минимумом - всего одним шагом процесса второго порядка, в котором за начальную матрицу принимается матрица, полученная в результате предыдущего (k-1)-го шага. Таким образом приходим к методу Ньютона с последовательной аппроксимацией обратных матриц:
(3.3.1)
где k = 0,1,2,…, а и - начальные вектор и матрица (). Этот метод (будем называть его более коротко ААМН - аппроксимаиионный аналог метода Ньютона) имеет простую схему вычислений - поочередное выполнение векторных в первой строке и матричных во второй строке его записи (3.3.1) операций. Скорость его сходимости почти так же высока, как и у метода Ньютона. Последовательность () может квадратично сходиться к решению уравнения F(x)=0 (при этом матричная последовательность () также квадратично сходится к , т.е. в нормально развивающемся итерационном процессе (3.3.1) должна наблюдаться достаточно быстрая сходимость () к нулю).
Применение той же последовательной аппроксимации обратных матриц к простейшему рекурсивному методу Ньютона (3.2.2) или, что то же, к двухступенчатому процессу (3.2.3) определяет его аппроксимацирнный аналог
(3.3.2)
как и (3.2.2), также можно отнести к- методам третьего порядка. Доказательство кубической сходимости этого метода требует уже более жестких ограничений на свойства F(х) и близость к , к , чем в предыдущем методе. Заметим, что к улучшению сходимости здесь может привести повышение порядка аппроксимации обратных матриц, например, за счет добавления еще одного слагаемого в формуле для подсчета :
.4 Разностный метод Ньютона
На базе метода Ньютона (3.1.2) можно построить близкий к нему по поведению итерационный процесс, не требующий вычисления производных. Сделаем это, заменив частные производные в матрице Якоби J(x) разностными отношениями, т.е. подставив в формулу (3.1.1) вместо матрицу где
При удачном задании последовательности малых векторов (постоянной или сходящейся к нулю) полученный таким путем разностный (или иначе, дискретный) метод Ньютона имеет сверхлинейную, вплоть до квадратичной, скорость сходимости и обобщает на многомерный случай метод. При задании векторного параметра h - шага дискретизации - следует учитывать точность машинных вычислений (macheps), точность вычисления значений функций , средние значения получаемых приближений.
3.5 Обобщение полюсного метода Ньютона на многомерный случай
Переложим вывод одномерного полюсного метода Ньютона на векторную основу. Касательную к кривой в точке () зададим условием ортогональности текущего вектора этой прямой и ее нормального вектора, в качестве которого можно взять вектор . Уравнение прямой, проходящей через полюс и связанную с уже известным приближением точку (), получим из условия коллинеарности текущего вектора этой прямой и ее направляющего вектора . Таким образом, точку пересечения двух прямых, проекцию которой на ось абсцисс считаем новым приближением , находим из совокупности условий
(3.5.1)
Первое из этих условий означает равенство нулю скалярного произведения (n,u), второе - пропорциональность соответствующих координат векторов v и l или, иначе, равенство нулю составленного из них определителя. Следовательно, искомое приближение есть первая компонента вектора, служащего решением линейной системы
(3.5.2)
(вторая компонента - ордината точки пересечения указанных прямых - после вычисления значения может дать информацию об отклонении от функции в точке ее локальной аффинной модели, каковой является проведенная в точке касательная). Ясно, что получаемое из системы (3.5.2) значение тождественно его.
Рассмотренный векторный подход к построению одномерного полюсного метода Ньютона служит ключом для его распространения на двумерный случай на основе таких же геометрических, но уже пространственных соображений.
Пусть требуется найти приближенное решение двумерной нелинейной системы в предположении непрерывной дифференцируемости входящих в нее функций f(x, у) и g(x, у) в некоторой области G, содержащей