"Метод Лобачевского-Греффе" для решения алгебраических уравн

[Sverest]

Объясните что такое "Метод Лобачевского-Греффе" для решения алгебраических уравнений, случай действительных корней

Какую литературу почитать на эту тему?

[chessar]

Березин И.С., Жидков Н.П. - Методы вычислений, Том 2, Глава 7, $\S$ 3 (стр. 103-128).

[Sverest]

Спасибо за учебник!

В этом учебнике на странице 106 (второй том) есть пример:
Рассмотрим в качестве примера решение методом Лобачевского уравнения:

$x^4-35x^3+380x^2-1350x+1000=0$

промежуточные вычисления в таблице:

$\begin{tabular}{c|c|r|r|r|r|r} m& &a_0&a_1&a_2&a_3&a_4 \\ \hline 0& &1&-35&380&-1350&10^3 \\ \hline & a_i^2&1&1225&144400&1822500&10^6 \\ & -2a_{i-1} a_{i+1}& &-760&-94500&-760000& \\ & 2a_{i-2} a_{i+2}& & &2000& & \\ \hline 1& &1&465&51900&1062500&10^6 \\ \hline & a_i^2&1&216225&269361 \cdot 10^4&112891 \cdot 10^7&10^{12} \\ & -2a_{i-1} a_{i+1}& &-103800&-98813 \cdot 10^4&-10380 \cdot 10^7& \\ & 2a_{i-2} a_{i+2}& & &200 \cdot 10^4& & \\ \hline 2& &1&112425&170748 \cdot 10^4&102511 \cdot 10^7&10^{12} \\ \hline \hline \end{tabular}$

$\begin{tabular}{c|c|r|r|r|r|r} m& &a_0&a_1&a_2&a_3&a_4 \\ \hline & a_i^2&1&1263938 \cdot 10^4&291549 \cdot 10^{13}&105085 \cdot 10^{19}&10^{24} \\ & -2a_{i-1} a_{i+1}& &-341496 \cdot 10^4&-23050 \cdot 10^{13}&-341 \cdot 10^{19}& \\ & 2a_{i-2} a_{i+2}& & &.... & & \\ \end{tabular}$

Странно в одной таблице если пишешь, выдает syntax error, пришлось на две разбить

Меня интересует почему в последней строке поставили 4 точки

[chessar]

Sverest в сообщении #615003 писал(а):

Меня интересует почему в последней строке поставили 4 точки

Видимо опустили, т.к. не влезает в ячейку.

Sverest в сообщении #615003 писал(а):

Странно в одной таблице если пишешь, выдает syntax error, пришлось на две разбить

Да, какие-то проблемы имеются с tabular, только у меня не Syntax Error выдаёт, а Source Not Found (может стоит в раздел по работе форума написать?). Вот array прекрасно справляется:
$\begin{array}{c|c|r|r|r|r|r} m& &a_0&a_1&a_2&a_3&a_4 \\ \hline 0& &1&-35&380&-1350&10^3 \\ \hline & a_i^2&1&1225&144400&1822500&10^6 \\ & -2a_{i-1} a_{i+1}& &-760&-94500&-760000& \\ & 2a_{i-2} a_{i+2}& & &2000& & \\ \hline 1& &1&465&51900&1062500&10^6 \\ \hline & a_i^2&1&216225&269361 \cdot 10^4&112891 \cdot 10^7&10^{12} \\ & -2a_{i-1} a_{i+1}& &-103800&-98813 \cdot 10^4&-10380 \cdot 10^7& \\ & 2a_{i-2} a_{i+2}& & &200 \cdot 10^4& & \\ \hline 2& &1&112425&170748 \cdot 10^4&102511 \cdot 10^7&10^{12} \\ \hline & a_i^2&1&1263938 \cdot 10^4&291549 \cdot 10^{13}&105085 \cdot 10^{19}&10^{24} \\ & -2a_{i-1} a_{i+1}& &-341496 \cdot 10^4&-23050 \cdot 10^{13}&-341 \cdot 10^{19}& \\ & 2a_{i-2} a_{i+2}& & &.... & & \\ \end{array}$

[Sverest]

Написано, что прекратить квадрирование нужно когда $c_i \approx b_i^2$
это я должен то что написано в строке $m=2$ сравнивать со строкой $m=1$?

[chessar]

Нет. В примере ведь 6 шагов (ну или 5, т.к. с 0 нумерация). А, кажется понял, там вместо точек получается $0{,}2\cdot10^{13}$ и для суммированния это слагаемое является несущественным. Собственно также и в остальных ячейках с точками.

[Sverest]

chessar в сообщении #615018 писал(а):

Нет. В примере ведь 6 шагов (ну или 5, т.к. с 0 нумерация). А, кажется понял, там вместо точек получается $0{,}2\cdot10^{13}$ и для суммированния это слагаемое является несущественным. Собственно также и в остальных ячейках с точками.

Как тогда определить когда закончить квадрирование, если другой пример будет?

[chessar]

"Нет" - это был ответ на то что точки означают не окончание алгоритма. А так всё правильно, останавливать, когда $c_i\approx b_i^2$.

[Sverest]

Написано $ z_1=402067 \cdot 10^{74}\;\; \lg z_1=79,6042985 $
Для чего это определяли, откуда взяли $\lg$, почему именно $\lg$?

$\frac{1}{64}\lg z_1=1,2438172$ откуда взяли $\frac{1}{64}$?

[chessar]

Что-то не особо как-то подробно расписан метод Лобачевского-Греффе. Описан и обоснован подробно ход одного шага квадрирования. А в общем алгоритм не расписан. Ну если почитать дальше, там где точность метода определяется, то вроде становится ясно. Мы квадрировали корни $m$ (в примере - это 6) раз - фактически в итоге возвели в степень $N=2^m$. Значит корни будут

\[x_i=z_i^{\frac{1}{N}}=\left(\frac{b_i}{b_{i-1}}\right)^\frac{1}{2^m}\]

А логарифмы взяты - видимо для удобство расчётов.
Всё-таки не очень в плане подробного описания алгоритма я Вам книгу посоветовал. Поищу что-нибудь ещё и обязательно напишу позже.

[Nacuott]

Есть еще книжица. I.Ф.Тесленко, О.М.Костовський
МЕТОД ЛОБАЧЕВСКОГО РОЗВ'ЯЗУВАННЯ АЛГЕБРАЇЧНИХ РІВНЯНЬ. (На Украинском языке)

[chessar]

Демидович Б.П., Марон И.А. Основы вычислительной математики.
Беланов А.А. Решение алгебраических уравнений методом Лобачевского. 1989.

[Sverest]

chessar в сообщении #615139 писал(а):

А логарифмы взяты - видимо для удобство расчётов.

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

[Sverest]

chessar в сообщении #615139 писал(а):

Мы квадрировали корни $m$ (в примере - это 6)

Откуда взялось 6?

$x_1$ находили так?


$\[x_1=\left(\frac{402067 \cdot 10^{74}}{1}\right)^\frac{1}{2^6}\]$

а потом $f(x_1)=-0,02$ как нашли?

[chessar]

Sverest в сообщении #627219 писал(а):

а потом как нашли?

Ну как откуда? 1-ая колонка таблицы (там даже написано $m$). Т.е. было выполнено 6 шагов квадрирования. А почему именно 6 шагов? Потому-что было (видимо) принято, что когда порядок чисел станет больше $10^{100}$, то нужно остановиться (смотреть по последней колонке). В другом источнике (Беланов А.А. Решение алгебраических уравнений методом Лобачевского. 1989) вроде бы там надо остановиться если будет больше $10^{50}$.

Sverest в сообщении #627219 писал(а):

находили так?

Да так, если конечно в скобочках у вас $z_i$ (я уже писал Вам формулу). Перед глазами нет той таблички, поэтому я не помню какой там $z_i$.

Sverest в сообщении #627219 писал(а):

Откуда взялось 6?

Ну уж я там не знаю как авторы нашли это - может подставили и на калькуляторе посчитали или еще как-то :).