PHP.SU

Программирование на PHP, MySQL и другие веб-технологии

PHP.SU Портал

Главная

Помощь

Поиск

Поиск Яндекс Вакансии

Пользователи

Здравствуйте, Гость

( Вход · Регистрация · Правила форума )

Забыли пароль?

Решение уравнений

Форумы портала PHP.SU » PHP » Пользовательские функции (Модераторы: valenok, ALEN)

Страниц (1): [1]

Описание: Класс для решения алгебраических уравнений до 5-й степени

Поиск в теме | Версия для печати

EuGen	Отправлено: 22 Января, 2013 - 14:04:24
Профессионал Покинул форум Сообщений всего: 9095 Дата рег-ции: Июнь 2007 Откуда: Berlin Помог: 707 раз(а)	Представляю вашему вниманию класс, который позволяет решать алгебраические уравнения до 4-й степени включительно в вещественных корнях аналитически известными методами. Для уравнений более высоких порядков существуют численные методы решения (я имею ввиду аппроксимирующие итерации по методам Рунге-Кутта) - возможно, в дальнейшем я добавлю такую возможность. Однако этот метод весьма ресурсоемок, аналитических же методов решения уравнений степени, превышающей 4, не существует ввиду того, что корни таких уравнений в общем случае не являются алгебраическими числами (то есть не выразимы в радикалах) - согласно теореме Абеля-Руфини. Для уравнений до 2-й степени включительно текущая версия класса так же позволяет получить решение в виде радикала, то есть указывается формула с подставленными числовыми значениями, по которой можно получить точное значение корня. Для уравнений 3-й и 4-й степени это так же возможно сделать, но вычисления проводятся по методам Виета и Феррари соответственно (от формулы Кардано я отказался по причине трудоемкости практического её применения из-за необходимости вариативных вычислений над полем комплексных чисел), что делает такие построения чересчур громоздкими и трудночитаемыми в терминах CLI-разделителей, а потому практически бесполезными. PHP: скопировать код в буфер обмена class Equation { const ROOT_EXACT = 'point'; const ROOT_RANGE = 'range'; const ROOT_RANGE_FROM = 'range_from'; const ROOT_RANGE_TILL = 'range_till'; const SOLVE_ALGEBRAIC = 1; const SOLVE_EXACT = 0; const FLOAT_EQUATION_DELTA = 1E-15; protected $_iPower = 0; protected $_rgCoef = array(); public function __construct() { $rgArgs = func_get_args(); if(!count($rgArgs)) { return null; } $rgCoef = is_array($rgArgs[0])?$rgArgs[0]:$rgArgs; $this->_iPower = count($rgCoef)-1; for($i=0; $i<=$this->_iPower; $i++) { $this->_rgCoef[$this->_iPower-$i] = $rgCoef[$i]; } $i=$this->_iPower; //strip zero-multiplied high powers, if any, with reducing whole power: while(!$this->_rgCoef[$i] && $i>0) { unset($this->_rgCoef[$i]); $i--; $this->_iPower--; } } public function solveEquation($mFlag=self::SOLVE_EXACT) { $sMethod = '_solve_power_'.$this->_iPower; if(method_exists($this, $sMethod)) { return $this->$sMethod($mFlag); } return null; } public function getAlgebraic($sVariable='z', $sPowerDelimiter='^') { $rgPrints = array(); $rgCoef = $this->_rgCoef; krsort($rgCoef); array_walk($rgCoef, function($fValue, $iKey) use (&$rgPrints, $sVariable, $sPowerDelimiter) { if($fValue) { $rgPrints[] = $iKey?($fValue!=1?$fValue:'').$sVariable.($iKey!=1?$sPowerDelimiter.$iKey:''):$fValue; } }); return str_replace('+ -','- ',join(' + ', $rgPrints)); } protected function _solve_power_0($mFlag=self::SOLVE_EXACT, $rgCoef=null) { $rgCoef=isset($rgCoef)&&is_array($rgCoef)?$rgCoef:$this->_rgCoef; if(!$rgCoef[0]) { return array( self::ROOT_RANGE=>array(self::ROOT_RANGE_FROM=>-INF, self::ROOT_RANGE_TILL=>INF), ); } else { return array(); } } protected function _solve_power_1($mFlag=self::SOLVE_EXACT, $rgCoef=null) { $rgCoef=isset($rgCoef)&&is_array($rgCoef)?$rgCoef:$this->_rgCoef; if($mFlag==self::SOLVE_ALGEBRAIC) { $sCoef = -1($rgCoef[0]/$rgCoef[1])<0?'-':''; $mResult = $rgCoef[0]?$sCoef.abs($rgCoef[0]).'/'.abs($rgCoef[1]):'0'; } else { $mResult = -1$rgCoef[0]/$rgCoef[1]; } return array(self::ROOT_EXACT=>array($mResult)); } protected function _solve_power_2($mFlag=self::SOLVE_EXACT, $rgCoef=null) { $rgCoef=isset($rgCoef)&&is_array($rgCoef)?$rgCoef:$this->_rgCoef; $fDiscriminant = pow($rgCoef[1],2)-4$rgCoef[0]$rgCoef[2]; if($this->_compare_floats($fDiscriminant, 0)) { $sCoef = -1($rgCoef[1]/$rgCoef[2])<0?'-':''; $mResult = $mFlag==self::SOLVE_EXACT?-1$rgCoef[1]/(2$rgCoef[2]):$sCoef.abs($rgCoef[1]).'/(2'.abs($rgCoef[2]).')'; return array( self::ROOT_EXACT=>array($mResult) ); } elseif($fDiscriminant<0) { return array(); } else { if($mFlag==self::SOLVE_EXACT) { $rgRoots = array( (-1$rgCoef[1]+sqrt($fDiscriminant))/(2$rgCoef[2]), (-1$rgCoef[1]-sqrt($fDiscriminant))/(2$rgCoef[2])); } else { $sCoefB = $this->_get_algebraic_sign_single(-1$rgCoef[1]); $sCoefA = $this->_get_algebraic_sign_single(-1$rgCoef[2]); $sCoefD = -1$rgCoef[2]$rgCoef[0]<0?'-':'+'; $sSummD = $rgCoef[0]?$sCoefD.'4'.abs($rgCoef[2]).''.abs($rgCoef[0]):''; $sSummB0= ''; $sSummB1= ''; if($rgCoef[1]) { $sSummB0 = $sCoefB.abs($rgCoef[1]); $sSummB1 = 'pow('.$rgCoef[1].',2)'; } $rgRoots = array( $sCoefA.'('.$sSummB0.'+sqrt('.$sSummB1.$sSummD.'))/(2'.$rgCoef[2].')', $sCoefA.'('.$sSummB0.'-sqrt('.$sSummB1.$sSummD.'))/(2'.$rgCoef[2].')' ); } return array(self::ROOT_EXACT=>$rgRoots); } } //Viett method on resolving 3-power equation protected function _solve_power_3($mFlag=self::SOLVE_EXACT, $rgCoef=null) { $rgCoef = isset($rgCoef)&&is_array($rgCoef)?$rgCoef:$this->_rgCoef; $fMajor = $rgCoef[3]; $rgCoef = array_map(function($fItem) use ($fMajor) { return $fItem/$fMajor; }, $rgCoef); $fQ = (pow($rgCoef[2],2)-3$rgCoef[1])/9; $fR = (2pow($rgCoef[2],3)-9$rgCoef[2]$rgCoef[1]+27$rgCoef[0])/54; $fS = pow($fQ,3)-pow($fR,2); if($fS>0) { $fPhi = acos($fR/pow($fQ,1/3))/3; $rgRoots= array( -2pow($fQ,1/2)cos($fPhi)-$rgCoef[2]/3, -2pow($fQ,1/2)cos($fPhi+2pi()/3)-$rgCoef[2]/3, -2pow($fQ,1/2)cos($fPhi-2pi()/3)-$rgCoef[2]/3, ); } elseif($fS<0) { if($fQ>0) { $fPhi = acosh(abs($fR)/$this->_get_algebraic_root(pow(abs($fQ),3),2))/3; $rgRoots= array(-2$this->_get_sgn($fR)$this->_get_algebraic_root(abs($fQ),2)cosh($fPhi)-$rgCoef[2]/3); } else { $fPhi = asinh(abs($fR)/$this->_get_algebraic_root(pow(abs($fQ),3),2))/3; $rgRoots= array(-2$this->_get_sgn($fR)$this->_get_algebraic_root(abs($fQ),2)sinh($fPhi)-$rgCoef[2]/3); } } else { if($fR) { $rgRoots=array( -2$this->_get_algebraic_root($fR,3)-$rgCoef[2]/3, $this->_get_algebraic_root($fR,3)-$rgCoef[2]/3 ); } else { $rgRoots=array(-1$rgCoef[2]/3); } } $rgRoots = array_map(function($fItem) { return $this->_compare_floats(round($fItem), $fItem)?round($fItem):$fItem; }, $rgRoots); return array(self::ROOT_EXACT=>$rgRoots); } //Ferrari method of resolving 4-power equation protected function _solve_power_4($mFlag=self::SOLVE_EXACT, $rgCoef=null) { $rgCoef = isset($rgCoef)&&is_array($rgCoef)?$rgCoef:$this->_rgCoef; $fAlpha = (-3pow($rgCoef[3],2))/(8pow($rgCoef[4],2))+$rgCoef[2]/$rgCoef[4]; $fBeta = pow($rgCoef[3],3)/(8pow($rgCoef[4],3))-($rgCoef[3]$rgCoef[2])/(2pow($rgCoef[4],2))+$rgCoef[1]/$rgCoef[4]; $fGamma = (-3pow($rgCoef[3],4))/(256pow($rgCoef[4],4))+pow($rgCoef[3],2)$rgCoef[2]/(16pow($rgCoef[4],3))-$rgCoef[3]$rgCoef[1]/(4pow($rgCoef[4],2))+$rgCoef[0]/$rgCoef[4]; $rgRoots = array(); if($this->_compare_floats(0, $fBeta)) { if(($fResolventaD = pow($fAlpha,2)-4$fGamma)<0) { return array(); } if(($fSqrtNeg = -1$fAlpha-$this->_get_algebraic_root($fResolventaD, 2))>=0) { $rgRoots = array_merge($rgRoots, array( -1$rgCoef[3]/(4$rgCoef[4])+$this->_get_algebraic_root($fSqrtNeg/2, 2), -1$rgCoef[3]/(4$rgCoef[4])-$this->_get_algebraic_root($fSqrtNeg/2, 2) )); } if(($fSqrtPos = -1$fAlpha+$this->_get_algebraic_root($fResolventaD, 2))>=0) { $rgRoots = array_merge($rgRoots, array( -1$rgCoef[3]/(4$rgCoef[4])+$this->_get_algebraic_root($fSqrtPos/2, 2), -1$rgCoef[3]/(4$rgCoef[4])-$this->_get_algebraic_root($fSqrtPos/2, 2) )); } } else { $fP = -1pow($fAlpha,2)/12-$fGamma; $fQ = -1pow($fAlpha,3)/108+$fAlpha$fGamma/3-pow($fBeta,2)/8; if(($fResolventaD = pow($fQ,2)/4+pow($fP,3)/27)<0) { return array(); } $fR = -1$fQ/2+$this->_get_algebraic_root($fResolventaD, 2); $fU = $this->_get_algebraic_root($fR, 3); $fY = -5$fAlpha/6+$fU+($fU?((-1$fP)/(3$fU)):(-1$this->_get_algebraic_root($fQ, 3))); if(($fW = $fAlpha+2$fY)<0) { return array(); } $fW = $this->_get_algebraic_root($fW, 2); if(($fSqrtNeg = -1(3$fAlpha+2$fY-2$fBeta/$fW))>=0) { $rgRoots = array_merge($rgRoots, array( -1$rgCoef[3]/(4$rgCoef[4])+(-1$fW+$this->_get_algebraic_root($fSqrtNeg, 2))/2, -1$rgCoef[3]/(4$rgCoef[4])+(-1$fW-$this->_get_algebraic_root($fSqrtNeg, 2))/2 )); } if(($fSqrtPos = -1(3$fAlpha+2$fY+2$fBeta/$fW))>=0) { $rgRoots = array_merge($rgRoots, array( -1$rgCoef[3]/(4$rgCoef[4])+($fW+$this->_get_algebraic_root($fSqrtPos, 2))/2, -1$rgCoef[3]/(4$rgCoef[4])+($fW-$this->_get_algebraic_root($fSqrtPos, 2))/2 )); } } //since Ferrari method have no guarantee from duplicate roots, do following: $rgRoots = array_unique(array_map(function($fItem) { return $this->_compare_floats(round($fItem), $fItem)?round($fItem):$fItem; }, $rgRoots)); return array(self::ROOT_EXACT=>$rgRoots); } protected function _compare_floats($fLeft, $fRight) { return abs((double)$fLeft-(double)$fRight)<self::FLOAT_EQUATION_DELTA; } //Sign functions: //for string representation: protected function _get_algebraic_sign_single($fNumeric) { return $fNumeric<0?'-':''; } //for exact calculation: protected function _get_sgn($fArg) { if($fArg<0) { return -1; } return 1; } //since pow(x,1/N) didn't work properly, function below is needed: protected function _get_algebraic_root($fArg, $iRoot) { if(!is_int($iRoot)) { return null; } if(!$iRoot) { return $fArg?1:NaN; } if($fArg>=0) { return pow($fArg, 1/$iRoot); } else { if($iRoot%2) { return -1pow(abs($fArg), 1/$iRoot); } else { return NaN; } } } } Пример использования: equation.php: PHP:* скопировать код в буфер обмена //includes omitted $rEquation = new Equation(explode(',', $_SERVER['argv'][1])); echo($rEquation->getAlgebraic()."\n"); var_dump($rEquation->solveEquation(Equation::SOLVE_EXACT)); Результаты: CODE (bash): скопировать код в буфер обмена user@host:/path$ php equation.php 1,-10,35,-50,24 z^4 - 10z^3 + 35z^2 - 50z + 24 array(1) { ["point"]=> array(4) { [0]=> float(3) [1]=> float(2) [2]=> float(4) [3]=> float(1) } } user@host:/path$ php equation.php 1,0,1 z^2 + 1 array(0) { } user@host:/path$ php equation.php 1,-6,11,-6 z^3 - 6z^2 + 11z - 6 array(1) { ["point"]=> array(3) { [0]=> float(1) [1]=> float(3) [2]=> float(2) } } Важно - повторные корни фильтруются, поэтому вырожденные случаи полиномов будут возвращать меньше корней, чем степень полинома (это же касается остальных случаев). ----- Есть в мире две бесконечные вещи - это Вселенная и человеческая глупость. Но насчет первой .. я не уверен.

DeepVarvar	Отправлено: 22 Января, 2013 - 14:34:41
Активный участник Покинул форум Сообщений всего: 10377 Дата рег-ции: Дек. 2008 Откуда: Альфа Центавра Помог: 353 раз(а)	EuGen пишет: ... Рунге-Кутта ... Я не знаю таких "страшных" слов, не довелось в свое время узнать. Да и алгоритмов решения того, что скрыто в этих "страшных" словах тоже не знаю. Зато мне нравится "оформление" класса и подход к реализации. Но есть вопрос: А где же всетаки может такая штука пригодиться, например мне. (просто интересно пощупать и разобраться в алгоритмах, а использовать негде) ----- Шта? Репозиторий?

EuGen	Отправлено: 22 Января, 2013 - 14:45:00
Профессионал Покинул форум Сообщений всего: 9095 Дата рег-ции: Июнь 2007 Откуда: Berlin Помог: 707 раз(а)	Проблема решения уравнений 4-й степени и выше возникает, например, в таких алгоритмах компьютерной графики, как обратная трассировка. Так, для того, чтобы выполнить трассировку тора с бесконечным числом преломлений, нужно решить такое уравнение в вещественных корнях. В вебе, наверное, этого не нужно будет делать. По крайней мере с ходу задача в голове не возникает (ровно как она не возникла за долгие годы работы). Однако же, как и в случае с, например, выложенным в этой же ветке, но в соседней теме "Конверторе диапазонов", решение носит больше аналитический характер и удовлетворяет мой академический интерес. Насчет оформления - есть некоторые элементы, которые были "доделаны второпях" (например, у метода вывода уравнения для печати значения по-умолчанию для аргументов заданы прямо в объявлении, вместо того, чтобы быть сделанными как константы, как это есть в остальных местах класса). Кроме того, я "сэкономил" на вызове исключений (к примеру, при проверке внутри метода решения я опираюсь на то, что старший коэффициент всегда отличен от нуля, но, строго говоря, метод этого знать не может и не должен, а я же - знаю, так как фильтрую коэффициенты и степень уравнения в конструкторе). Уверен, видя достаточно высокую громоздкость вычислений, читатели простят мне такие оплошности. DeepVarvar Если Вам это интересно, то вкратце ситуация обрисована в: Формула Кардано для решения кубического уравнения Метод Виета для тригонометрического получения корней кубического уравнения Метод Феррари для решения уравнения 4-й степени при помощи получения резольвенты с последующим её разрешением. Теорема Абеля-Руфини, утверждающая, что уравнение степени N не имеет выразимых в радикалах корней при N>4 в общем случае, и опирающаяся на теорию групп Галуа ----- Есть в мире две бесконечные вещи - это Вселенная и человеческая глупость. Но насчет первой .. я не уверен.

DeepVarvar	Отправлено: 22 Января, 2013 - 14:58:12
Активный участник Покинул форум Сообщений всего: 10377 Дата рег-ции: Дек. 2008 Откуда: Альфа Центавра Помог: 353 раз(а)	EuGen пишет: В вебе, наверное, этого не нужно будет делать Жаль... EuGen пишет: я "сэкономил" на вызове исключений Я тоже всегда на оных экономлю, правда не в тех местах где проверяются входные данные. EuGen пишет: вместо того, чтобы быть сделанными как константы А они подразумевают возможность "настройки", или это просто дань "моде", вынести что-то в константы класса? Эхх, пойду хоть почитаю про все эти "страшные" слова... ----- Шта? Репозиторий?

EuGen	Отправлено: 22 Января, 2013 - 15:05:06
Профессионал Покинул форум Сообщений всего: 9095 Дата рег-ции: Июнь 2007 Откуда: Berlin Помог: 707 раз(а)	DeepVarvar пишет: А они подразумевают возможность "настройки", или это просто дань "моде", вынести что-то в константы класса? Конечно. Возможно, Вы захотите изменить логику функции и подставлять не z, а x - а степень выводить при помощи <sup>..</sup> - класс ведь может использоваться и на веб-страницах. Правда, для последнего придется немного адаптировать вывод (повторюсь, этот метод дописывался немного "впопыхах"), но тем не менее - идея в этом. DeepVarvar пишет: Эхх, пойду хоть почитаю про все эти "страшные" слова... Это вовсе не обязательно ввиду EuGen пишет: В вебе, наверное, этого не нужно будет делать - так что стоит почитать, только если в самом деле интересно. Здесь затрагиваются вопросы высшей алгебры, теории комплексных чисел, дискретного и функционального исчислений, так что "разобраться во всем" - значит получить математическое образование, на что могут уйти годы. Это вовсе не обязательно и никак не влияет на профессионализм веб-разработчика. ----- Есть в мире две бесконечные вещи - это Вселенная и человеческая глупость. Но насчет первой .. я не уверен.

DeepVarvar	Отправлено: 22 Января, 2013 - 15:06:59
Активный участник Покинул форум Сообщений всего: 10377 Дата рег-ции: Дек. 2008 Откуда: Альфа Центавра Помог: 353 раз(а)	EuGen пишет: Это вовсе не обязательно и никак не влияет на профессионализм веб-разработчика Я считаю что влияет и как-то мне стыдновато ----- Шта? Репозиторий?

caballero	Отправлено: 22 Января, 2013 - 15:17:41
Активный участник Покинул форум Сообщений всего: 5998 Дата рег-ции: Сент. 2011 Откуда: Харьков Помог: 126 раз(а)	начни со школьной программы - метод Ньютона, метод хорд. Потом плавно перейдешь к методу Эйлера и более страшным словам. вообще - высшая математика редко встречается в прикладном программировании. а если и встретится то это будет скорее задача какой нибудь оптимизации и не с отдельным уравнением а с системмой нелинейных уравнений. А там уже матрица Якоби и прочие продвинутые штуки. Впрочем все эти алгоритмы уже давно отработаны еще на старом добром фотране. Есть куча сишных библотек. На похапе такое решать никто не будет - конект по таймауту разорвется быстрее чем матрица досчитается. ----- Бесплатная система складского учета с открытым кодом https://zippy[dot]com[dot]ua/zstore

Поиск в теме | Версия для печати

Страниц (1): [1]

Сейчас эту тему просматривают: 0 (гостей: 0, зарегистрированных: 0)

« Пользовательские функции »

Все гости форума могут просматривать этот раздел.
Только зарегистрированные пользователи могут создавать новые темы в этом разделе.
Только зарегистрированные пользователи могут отвечать на сообщения в этом разделе.