2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему
 
 Модифицированный метод Грама-Шмидта
Сообщение01.09.2022, 22:29 


31/08/22
183
Здравствуйте. Всем доброго здоровья и хорошего настроения.
Прошу помощи в реализации модификации алгоритма Грама-Шмидта.
Изучаю алгоритмы QR декомпозиций.
Уже разобрался и написал в маткаде рабочую программу для классического метода Грама-Шмидта а так же метода вращений Гивенса. Все работает.
К методу отражений Хаусхолдера еще не приступал.
Хочу реализовать модифицированный метод Грама-Шмидта, перечитал все статьи что можно сходу найти, пересмотрел все обучающие видео и общая идея модификации в целом понятна (но не в деталях), развернуть сумматор в цикл чтобы накапливать меньше ошибок. Но реализовать не получается. Попыток предпринял массу прежде чем создать эту тему.
Правила форума прочитал, но так и не понял корректно ли выкладывать программы маткада в виде картинок? Гугл показал что так делают. Надеюсь и меня не будете расстреливать за это.
Привожу рабочую программу метода Грамма-Шмидта
Изображение
А вот последняя попытка сделать модификацию
Изображение
А это файл маткада
https://disk.yandex.ru/d/FelyDzm5Qwqp0Q

Конкретно непонятно что и как инициализировать в начале а так же что по чему итерируется.
Как можно свернуть изображения? теги спойлер и офф не работают.

ПС: Я не студент. Программирование, машинное обучение это мои хобби. Пишу в этот раздел потому что вопрос не в программировании а в математике.
ORIGIN обязательно делаю равным 0, чтобы код в последствии можно было легко перенести на C#.

 Профиль  
                  
 
 Re: Модифицированный метод Грама-Шмидта
Сообщение02.09.2022, 00:42 
Заслуженный участник
Аватара пользователя


23/07/08
10909
Crna Gora
Schrodinger's cat в сообщении #1563946 писал(а):
ORIGIN обязательно делаю равным 0
Отлично, тогда и я начну нумеровать замечания с нуля.

0) Фамилия Грам пишется с одной «м», Вы местами пишете с двумя.

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

2) Программа для модифицированного метода содержит ошибку. В начале программы все векторы $e^{(i)}$ инициализируются нулями. Посмотрите на строку
$e^{(i)}\gets e^{(i)}-(e1^{(j)}\cdot e^{(i)})\cdot e1^{(j)}$
Очевидно, что если вектор $e^{(i)}$ до выполнения этого оператора нулевой, он и после него будет нулевым. Поскольку векторы $e^{(i)}$ при $i>0$ меняются только этим оператором, они так и остаются нулевыми.

3)
Schrodinger's cat в сообщении #1563946 писал(а):
Конкретно непонятно что и как инициализировать в начале
Какие-то инициализации следуют из описания алгоритма, какие-то сами собой разумеются (обнулить переменную для суммы перед суммированием), а что-то вообще не надо инициализировать. Из хорошего описания алгоритма всё должно быть понятно.
Schrodinger's cat в сообщении #1563946 писал(а):
а так же что по чему итерируется
Что это значит?
Schrodinger's cat в сообщении #1563946 писал(а):
Как можно свернуть изображения? теги спойлер и офф не работают.
Тег off работает, только (почему-то) не при просмотре редактируемого сообщения, а после отправки.

 Профиль  
                  
 
 Re: Модифицированный метод Грама-Шмидта
Сообщение02.09.2022, 13:47 


31/08/22
183
0) Благодарю за указание на мою невнимательность.
1) Так как все это делается для QR алгоритма счел уместным это оставить для полноты картины. Возможно стоило выделить проблемный участок или пояснить словами, приму на будущее. Полагал, что слова "модификации алгоритма Грама-Шмидта" выделят необходимое.
2) Участок модификации и не претендовал на правильность, приведен последний код который я пробовал, но он выдает неверные результаты.
То что вы написали очевидно и мне.
3)
svv в сообщении #1563956 писал(а):
Из хорошего описания алгоритма всё должно быть понятно

Поделитесь пожалуйста "хорошим описанием".

svv в сообщении #1563956 писал(а):
Тег off работает

Спасибо, учту.

Вот наиболее понятная для меня запись алгоритма (из тех что я находил). Ссылка на Википедию.
Параграф "Численная стабильность", первая строка алгоритма
$u_{k}^{(1)}=v_{k}-proj_{u_{1}}(v_{k})$
Вопросы:
0) $v_{k}$ это столбец моей матрицы $A$ я верно понимаю? (Вопрос может быть и тупой, так как выше приведен алгоритм не модифицированного алгоритма из которого следует что это так. Но хотел бы формального подтверждения.)
1) $u_{k}^{(1)}$ как понимать $(1)$?
2) Можно перезаписывать туже матрицу $u$ или для каждой итерации нужно создавать новую?
3) Что такое $u_{1}$? На нулевой итерации никаких $u$ еще не вычислено, как я могу рассчитать что-то из того же самого?
4) Предварительная инициализация остается та же что и в не модифицированном варианте? (Но я пробовал, не получалось.)
Эти вопросы в большей степени у меня возникают из-за того, что тут приведен вырезанный кусок а не алгоритм в целом.
Ну и да, я понимаю, что тут все нумеруется от 1, для меня требуется поправка от 0.

 Профиль  
                  
 
 Re: Модифицированный метод Грама-Шмидта
Сообщение02.09.2022, 19:10 


31/08/22
183
Все, разобрался.
Спасибо за помощь.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 4 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group