Приблеженное решение системы уравнений

Помогите пожалуйста.
Может кто-нибудь сможет предложить идеи как решить систему уравнений из n ур-й с n неизвестными. Система следующая:

f1(x1,x2,x3,...,xn)=0;
f2(x1,x2,x3,...,xn)=0;
...
fn(x1,x2,x3,...,xn)=0;

Функции f1...fn известны неявно. То есть для любого х известен f(x), но сама функция произвольная. Естественно систему надо решить приближенно (с точностью eps).

В принципе с алгоритмами решения уравнения от одной неизвестной я знаком (алгоритм ньютона, деления пополам, итерации, пропорциональных отрезков), но применить их никак не получается!

Жду каких нибудь идей.

А чем метод Ньютона не устраивает? (в векторном варианте, есесно)
Метод требует вычисления производных dfi/dxj. Если функции f неявные, производные можно
считать численно. Если предположить, что матрица
A(i,j)=(dfi/dxj)(x1,x2,...xn)
невырожденная, то метод записывается так (k-номер итерации x-само собой,вектор)
x(k+1)=x(k) - Ainv(x(k)) * f(x(k));
(Ainv-обратная от A)
Условие завершения - норма |x(k) - x(k-1)| <= epsilon

wbr

Сообщение отредактировано: Barrett - 30.11.03, 16:31

Полностью писоединяюсь к Barrett'у, только хотелось бы заметить:

Что конечно требует непрерывность функций и, желательно, гладкость. То есть в самом худшем случае придется интерполировать для вычисления наиболее точной производной в точках разрыва и переломов.

Сообщение отредактировано: Дмитрий - 30.11.03, 19:05

Дело в том что на сколько я помню метод Ньютона, он не все функции позволяет вычислять Функцию вида sgn(x)*sqrt(|x|) он не вычеслит если начальное значение по иксу к примеру 10. Или может я не догоняю метод?

ИМХО Правило Крамера

Что конечно требует непрерывность функций и, желательно, гладкость. То есть в самом худшем случае придется интерполировать для вычисления наиболее точной производной в точках разрыва и переломов.

производная в точке разрыва


ужас!!!

за такое надо в школу возвращать

Очень медленный метод, но позволит избежать вычисление производных, и следовательно неприятностей связанных с разрывами функций.
Заменяем задачу поиска корня на задачу поиска минимума, т.е. вместо

f1(x1,x2,x3,...,xn)=0;
..............................
записываем

min f1^2(x1,x2,x3,...,xn)+f2^2(x1,x2,x3,...,xn)
..............................

точка глобального экстремума и будет решением. Для поиска мининимума следует использовать симплекс метод (он же метод многогранника). Когда экстремум найден, надо проверять его близость к 0, если условие не выполнено, то генерировать случайным образом новые стартовые значения и вновь искать экстремум.

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

2lamachok: Правило крамера тут не при чем! Никто не говорит что у нас функции являются линейными многочленами! И вообще вся алгебра здесь непременима!

2PAV : а как ты будешь точку минимума считать то? Перебором что-ли или есть специальные методы.

2Дмитрий : такую функцию я взял для примера. На самом деле эта функция есть ни что иное как гипербола повернутая на -pi/2. Вот если действовать там методом Ньютона, то с первого же раза (шага) мы промохнемся мима корня, и каждый раз будем промахиваться все сильнее и сильнее. Все дальше и дальше уходить от нуля.

P.S. Кстати о функциях также известно, что они являются строгими относительно каждого параметра поотдельности.
То есть для любого x1<x2
f(a,b,...,x1,...,z)<f(a,b,...,x2,...,z) //то есть функция строго возрастающая
//Ну или наоборот знак ">" если функция строго убывающая

Жду еще предложений

Добавлено в 01.12.03, 17:25
Да и еще забыл : функции непрерывны... и дифферинцируемы.

Если известно, что

то сам бох велел метод Ньютона попробовать!

Метод простых итераций (с модификациями). Метод Брауна. Методы спуска.
(это я смотрю в книжку "Вержбицкий. Численные методы")

wbr

Сообщение отредактировано: Barrett - 01.12.03, 20:24

to shob_vas
Еще раз

. Метод широко известен, например см. Калиткин 'Численные методы'. Недостатки -- медленная сходимость, достоинства простота реализации возможность искать минимум на разрывных функциях многих переменных.

Если разрывов нет, то прямое решение методом Ньютона, или квазиньютоновские методы для поиска минимума. Кстати и прямой метод и поиск экстремума по времени сопоставимы, а при использовании поска экстемума квазиньютоновскими методами возможени даже выигрыш, т.к.
вычисление производных производится реже. см. Гилл, Мюррей, Райт "Практическая оптимизация".

Сообщение отредактировано: PAV - 03.12.03, 10:46

Производная выводится через касательную! Проведи касательную к одной точке...

* - график sign(x)

Производная выводится через касательную! Проведи касательную к одной точке...

* - график sign(x)

производная в этой точке

НЕ СУЩЕСТВУЕТ, НЕ СУЩЕСТВУЕТ

я поэтому не собираюсь её вычислять!

для того что бы она сущ-ла необходимо и достаточно чтобы сущ-ли два некоторых предела,справа и слева , и они были равны

и если произ-я сущ-ет то фун-я в этой точке непрерывна
поэтому производ-я в точке разрыва звучит абсурдно

ее просто нет в точке разрыва


но есть субдифференциал
(да Пав?)

Сообщение отредактировано: esperanto - 05.12.03, 11:06

2tserega
Так вот для таких вот точек либо вводятся фиктивные производные, либо аналитически рассматриваются уже две (или более) задачи вместо одной. Но второй вариант требует знать о точках разрыва уже в процессе написания программы. А так, можно немного эти места сгладить некой апроксимацией.

2snob_vas
прошу прощения за офтопик

to esperanto
Угу. Правда немного напоминает старый сюжет из "Ералаш"-а о доказательстве непересечения двух параллельных прямых в евклидовом пространстве.

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