Решение СЛАУ

From

Evgenij Masherov (2:5020/175.2)

To

Andrew Kuksov

Date

2003-01-14T09:27:25Z

Area

RU.ALGORITHMS

From: "Evgenij Masherov" <EMasherow@nsi.ru>

Mon Jan 13 2003 13:42, Andrew Kuksov wrote to Evgenij Masherov:

 EB>>>> Нет ли у кого-нибудь хорошего алгоритма сабж(на худой конец нахождения
 EB>>>> обратной матрицы). Матрица в идеале должна быть приличнных размеров,
 EB>>>> поэтому и алгоритм должен быть более менее шустрым.
 IR>>>    А кроме Гаусса ничего нету. По-крайней мере из точных методов. А
 IR>>> Гаусс  - n^3.

 AK> А так ли плох n^3? Ведь, скажем, для n=1000 все еще замечательно.
 AK> Интеpесно, в каких задачах pеально тpебуется лучший pезультат?

При однократном решении - возможно...
Но давайте рассмотрим задачу, где требуется решение многократное (пусть не
столь велика размерность).
Пусть у нас телефон, и хочется сжать данные для передачи. Один из подходов -
прогнозировать следующий отсчет и передавать только погрешность прогноза.
Прогноз будем делать линейной авторегрессией. Порядок модели возьмем всего 10.
Вот только прогноз этот придется делать 8000 раз в секунду. Причем делать - на
дешевом и/или малопотребляющем сигнальном процессоре. Есть основания полагать,
что Гаусс не справится (на самом деле здесь можно либо использовать специфику
обращаемой матрицы, и свести задачу к квадратичной сложности, либо
использовать приближенный алгоритм, вообще линейный, на чем и основаны
популярные стандарты сжатия АДИКМ)

Евгений Машеров АКА СанитарЖеня

--- ifmail v.2.15dev5
 * Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2)