Yuri Gendelman
За участие спасибо. С того я и начинал, что первым делом попытался ознакомиться с процедурами, включенными в известные библиотечные пакеты. На форум я гораздо позже написал, когда уже понял, что во всех библиотеках имеется, по существу, один и тот же стандартный набор возможностей. И на определенные мысли это меня, конечно, натолкнуло. А мысли вот такие.
Обширные пакеты программ создают в "общественном сознании" почти непреодолимое чувство, что на все вопросы уже найдены ответы. Кстати, точно то же самое впечатление возникает в головах обывателей по отношении к науке вообще. И лишь личная углубленность в какую-либо проблему позволяет осознать, насколько поверхностно то знание, которое считается непреложным.
Из учебника в учебник, из книги в книгу, из статьи в статью почти в буквальном пересказе перекочевывает материал, ставший классическим. Несомненно, что образовательным целям такая практика целиком отвечает. Однако, имеет вредный побочный эффект, выражающийся в замазывании подводных камней и рифов в алгоритмах. Доверяясь громкому имени капитана, пассажир считает все форватеры проходимыми. А зря!
Обращение к первоисточникам (в первую очередь к "СПРАВОЧНИК алгоритмов на языке Алгол. Линейная алгебра" под ред. Уилкинсона и Райнша, вышедшую в русском переводе еще в 1960 г.) показывает, что все нынешние алгоритмы взяты именно оттуда.
Математики придумывали алгоритмы на бумаге, а программисты затем перекладывали их на алгоритмические языки. Персональных компьютеров, я полагаю, тогда не было. А если и были ЭВМ, то авторы алгоритмов, по-видимому, к ним не обращались
. Сейчас, когда за шагами итерации можно удобно наблюдать на экране, многие утверждения авторов алгоритмов уже не кажутся такими непреложными.
Например, по утверждению Парлетта (Parlett B.N., The Symmetric Eigenvalue Problem, 1980) QL- алгоритм со сдвигом, равным собственному значению, сходится за одну итерацию (при точной арифметике). И он подсознательно полагал, что сойдется он именно к этому сдвигу. А вот наблюдение за процессом итерации на персоналке показывает, что процесс может сойтись вовсе не к тому СЗ, которое было выбрано в качестве сдвига, а к соседнему, если оно встретится на пути итерации раньше.
Величина первоначального сдвига (с которого начинается итерация) выбирается по оценке Уилкинсона, которая гарантирует сходимость. Но то, что итерация сойдется к СЗ, ближайшему к этой оценке, в общем случае неверно. Из-за этого мне не удается направить сходимость к желаемому мною СЗ. И все из-за того, что по дороге от краевого диагонального элемента к нужному мне значению СЗ могут встречаться (и почти всегда встречаются!) другие, не нужные мне СЗ. Такое почти всегда встречается, когда краевой элемент достаточно мал. И тогда на пути к максимальному СЗ будет суждено пройти почти через все остальные СЗ. И тут при каждом перешагивании может случиться так, что на кого-то наступишь. Тогда элемент на поддиагонали сразу же обнуляется и итерация вынужденно прекращается на том СЗ, на которое нечаянно наступил. Вот и получай тогда собственный вектор, которого не заказывал.
С бисекциями (алгоритм Штурма) тоже большая закавыка. Тут надо обязательно указывать ИНТЕРВАЛ, на котором ищешь СЗ. Но получается так, что невозможно указать такого интервала, чтобы в нем гарантированно было ровно 10 штук СЗ и не одной ни больше, и ни меньше. Ведь расстояния между соседними СЗ могут быть сколь угодно малы, не говоря уже о неточности их определения.
Хотя я все сильнее склоняюсь к тому, что использовать надо этот алгоритм, а не первый. Т.е. уповать на процедуру типа TINVIT и действовать в духе статьи
http://nadav.harel.org.il/papers/eigen.ps.gz
В общем, вопросов больше, чем ответов. А главное не видно никого, кто бы в эти вопросы захотел вникнуть – настолько велик всеобщий гипноз готовых алгоритмических решений.
