Форум на Исходниках.RU

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

PAV — Mon, 08 Dec 2003 11:13:01 +0000

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

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

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

Дмитрий — Fri, 05 Dec 2003 11:17:41 +0000

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

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

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

esperanto — Fri, 05 Dec 2003 11:05:10 +0000

esperanto:

Цитата (tserega @ 5.12.03, 06:28)

Цитата (Дмитрий @ 1.12.03, 15:30)

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

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

Цитата

^
1 |*************
|
-------------------*------------------------->
|
************| -1

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

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

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

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

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

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

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

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

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

tserega — Fri, 05 Dec 2003 07:28:12 +0000

tserega:

Цитата (Дмитрий @ 1.12.03, 15:30)

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

Цитата

^
1 |*************
|
-------------------*------------------------->
|
************| -1

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

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

PAV — Wed, 03 Dec 2003 10:38:36 +0000

PAV: to shob_vas
Еще раз

Цитата

Для поиска мининимума следует использовать симплекс метод (он же метод многогранника).

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

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

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

Barrett — Mon, 01 Dec 2003 20:23:20 +0000

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

Цитата

функции непрерывны... и дифферинцируемы.

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

Цитата

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

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

wbr

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

shob_vas — Mon, 01 Dec 2003 17:24:07 +0000

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

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

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

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

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

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

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

Дмитрий — Mon, 01 Dec 2003 13:30:10 +0000

Дмитрий:

Цитата (esperanto @ 1.12.03, 11:54)

производная в точке разрыва
ужас!!!

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

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

PAV — Mon, 01 Dec 2003 09:36:30 +0000

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

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

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

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

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

esperanto — Mon, 01 Dec 2003 08:54:01 +0000

esperanto:

Цитата (Дмитрий @ 30.11.03, 18:03)

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

Цитата (Barrett @ 30.11.03, 19:16)

Метод требует вычисления производных dfi/dxj.

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

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

ужас!!!

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

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

lamachok — Sun, 30 Nov 2003 23:11:37 +0000

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

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

shob_vas — Sun, 30 Nov 2003 19:23:46 +0000

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

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

Дмитрий — Sun, 30 Nov 2003 19:03:29 +0000

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

Цитата (Barrett @ 30.11.03, 19:16)

Метод требует вычисления производных dfi/dxj.

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

Barrett — Sun, 30 Nov 2003 16:16:56 +0000

Barrett: А чем метод Ньютона не устраивает? (в векторном варианте, есесно)
Метод требует вычисления производных 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

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

shob_vas — Sun, 30 Nov 2003 15:20:34 +0000

shob_vas: Помогите пожалуйста.
Может кто-нибудь сможет предложить идеи как решить систему уравнений из 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).

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

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