2014 dxdy logo

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

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


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


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



Начать новую тему Ответить на тему
 
 Линейная система с теплицевой матрицей и константной RHS
Сообщение10.02.2020, 18:14 


11/08/18
363
Добрый день,

есть теплицева матрица $T \in \R^{n \times m}$ и константная правая часть $u \in \R^n$, хочу решить задачу наименьших квадратов вида $\min_x ||T x - u||_2^2$, и научиться быстро выражать $x$ через первую строку и столбец этой теплицевой матрицы. Понятно, что если $n=m$ можно использовать разложение обратной теплицевой в виде суммы двух треугольных. В наименьших квадратах все будет уже гораздо менее тривиальнее и все упрется в сингулярное разложение $T^T T$.

ИМХО, но тут должно быть какое-то везение и решение, возможно есть просто аналитическое.

В общем случае, у меня задача интегральная: имея

$$\forall y \in [-M, M]: ~~ \int_{-L}^{L} f(x) u(x-y) dx = 1, ~~ \infty > L \ge M > 0 $$

необходимо выразить $f(x)$ через $u(x)$.

Вдруг тут есть какое-то очень простое и красивое решение, пожалуйста, посоветуйте!

Спасибо!

 Профиль  
                  
 
 Re: Линейная система с теплицевой матрицей и константной RHS
Сообщение10.02.2020, 21:26 


11/08/18
363
А такую задачу в Mathematica или Maple можно скормить, чтобы этот пакет решил? Я сам не придумал как, но вдруг можно?

 Профиль  
                  
 
 Re: Линейная система с теплицевой матрицей и константной RHS
Сообщение11.02.2020, 08:25 
Заслуженный участник
Аватара пользователя


11/03/08
9496
Москва
А в сторону Фурье не?

 Профиль  
                  
 
 Re: Линейная система с теплицевой матрицей и константной RHS
Сообщение11.02.2020, 10:04 


11/08/18
363
Если бы $L$ бы бесконечностью была бы, то да, Фурье - оно самое то.

Была идея воспользоваться тем, что производная от единицы по $y$ равна нулю, и рассматривать вместо $u$ ее производную по $y$. Вместо линейной системы надо тогда минимальное собственное значение искать и соответствующий вектор, что вроде примерно одинаково по арифметической сложности. Хочется чего-то красивого, но, пока, ничего не получается.

 Профиль  
                  
 
 Re: Линейная система с теплицевой матрицей и константной RHS
Сообщение11.02.2020, 10:49 
Заслуженный участник
Аватара пользователя


11/03/08
9496
Москва
А составить паровозик из вагончиков длины $2L$?

-- 11 фев 2020, 11:01 --

Или я вовсе куда-то не туда усложняю? В рамках поставленной задачи в качестве $f(x)$ вообще сгодится нормирующая константа. Может, уточнить условие?

 Профиль  
                  
 
 Re: Линейная система с теплицевой матрицей и константной RHS
Сообщение11.02.2020, 11:35 
Заслуженный участник


03/01/09
1677
москва
Для произвольной функции $u(x)$ решения может и не быть. Пусть, например, $u(x)=e^x$, подставив в уравнение, получим противоречие:$$e^{-y}=1,\forall y \in [-M,M]$$

 Профиль  
                  
 
 Re: Линейная система с теплицевой матрицей и константной RHS
Сообщение11.02.2020, 11:54 


10/03/16
3871
Aeroport
ilghiz в сообщении #1439204 писал(а):
хочу решить задачу наименьших квадратов вида $\min_x ||T x - u||_2^2$, и научиться быстро выражать $x$ через первую строку и столбец этой теплицевой матрицы.

Т.е. решение вашей задачи не зависит от большей части элементов матрицы, а только от элементов одной строки и одного столбца? Это как? :shock:

 Профиль  
                  
 
 Re: Линейная система с теплицевой матрицей и константной RHS
Сообщение11.02.2020, 11:57 
Заслуженный участник


23/07/08
10626
Crna Gora
Так она же тёплицева, она вся определяется первой строкой и столбцом.

 Профиль  
                  
 
 Re: Линейная система с теплицевой матрицей и константной RHS
Сообщение11.02.2020, 12:23 


11/08/18
363
Огромное спасибо за обсуждения! На самом деле у меня задача немного по-сложнее, но с частным случаем для $u$:

$$ \forall y \in [-M,M]: \int_{-L}^{L} \left( f_1(x) u_1(x-y) +  f_2(x) u_2(x-y) \right) dx = 1, 0 < M \le L < \infty$$

более того, по физике задачи, $2M \le L$, а

$$u_1(Z) = \frac{ 3 R Z} {(R^2 + Z^2)^{5/2}}$$

$$u_2(Z) = \frac{R^2 - 2 Z^2} {(R^2 + Z^2)^{5/2}}$$

где $R>0$ какой-то на перед заданный параметр.

Из еще дополнительного, мне
1. и/или нужна гладкость и минимизация квадрата производной искомых функций $f_1(x)$, $f_2(x)$,
2. и/или (еще хуже!!!) чтобы $f_1^2(x)+f_2^2(x)=1$.

Итого, для любых на перед заданных $L,M,R$ я ищу эти пары $f_1(x)$, $f_2(x)$ с одним или двумя дополнительными условиями (гладкость или единичность).

Для условия гладкости численную решалку написал, работает, но мне надо много (все возможные $L,M,R$ из довольно большого диапазона найти), и уже могу не дождаться решения с той точностью, что мне надо, а с обоими условиями, пока даже еще не решился чем минимизироваться.

Идея иметь какое-то аналитическое решение очень возбуждает, поэтому тут и вопрошаю.

Вдруг у кого будут какие-то идеи, пожалуйста, пните меня в правильном направлении!

 Профиль  
                  
 
 Re: Линейная система с теплицевой матрицей и константной RHS
Сообщение14.02.2020, 11:46 
Заслуженный участник


10/01/16
2315
ilghiz
Общее впечатление от задачи: безнадёга...
Вот некоторые соображения.
1. Про интегральное уравнение-1
1.1. Дифференцирование.
Если уравнение допускает дифференцирование по игрек, то имеем: надо найти эф, ортогональную (в Эль-2 на минус-эль-эль) всем производным от "у" (и не ортогональную самой "у"). Частные случаи:
1.1.1. $u$ - многочлен (степени 3, например). Частное решение - ортогонализируем систему $\{1,x,x^2,x^3\}$, в качестве $f$ берем четвертый вектор (с множителем); всего решений - до фига (общее решение получаем из частного, добавляя к нему произвольную функцию, ортогональную подпространству многочленов степени не выше 3).
1.1.2. $u$ - квазимногочлен (т.е., комбинация экспонент с коэффициентами-многочленами). Такое $u$ есть решение линейного однородного диф. ур-я с постоянными к-тами. Его производные порождают конечномерное подпространство. Если само $u$ есть линейная комбинация его производных - то решений нет! (Простейший пример такого типа уже указал ранее mihiv).
1.1.$\frac{3}{2}$. Гибрид двух предыдущих - дает разрешимость, с большим кол-вом решений.
1.1.3. Общий случай. Аппроксимируем заданную $u$ многочленами, и запустим процедуру из п. 1.1.1. Надежда получить решение - совершенно иллюзорна, хотя бы из-за примеров 1.1.2.
1.2. Основной путь - ряды Фурье. Разлагая $u$ в ряд Фурье на $[-2L,2L] $$f$ - на $[-L,L]$), и перераскладывая "неправильные" (с нечетными номерами) экспоненты, получим (бесконечную) систему линейных уравнений на к-ты $f$ (с "теплициевой" матрицей. Видимо, ТС так и делал). Разрешимость полученной системы крайне сомнительна (а "обрезание" ее, решение "обрезанной" и надежда на сходимость - тож) - см. ниже.
1.3. Вообще-то, мы имеем дело с классическим интегральным уравнением первого рода (разве что только ядро вполне себе специфично). Что мы знаем: соответствующий интегральный операрор - компактен.
Если он - конечномерный - попадаем в п. 1.1.1-1.1.2.
Но вот если - нет -- караул... За исключением специально подобранных случаев, (а конкретные функции ТС на такое как-то не тянут) решение не получить. Задача, как мы знаем, некорректна; поэтому всякие аппроксимации, как правило, ничего не дают: нет сходимости.

2. Уравнение-2. Как я понимаю, сдвигами аргумента эту задачу можно свести к задаче-1 (рассматривая функцию $f$, равную $f_1$ на одном участке оси, и равную (сдвинутой) $f_2$ на другом, с соответствующим надругательством над $u$). Поэтому выводы про задачу-1 остаются справедливыми и для задачи-2

 Профиль  
                  
 
 Re: Линейная система с теплицевой матрицей и константной RHS
Сообщение24.02.2020, 00:07 


11/08/18
363
Огромное спасибо, DeBill,

похоже Вы правы, сам к этому добавить ничего не могу, и, пока решаю численно. По численному решению - основная неприятность в том, что надо перебрать уйму параметров и для каждого такого набора параметров решить нелинейную систему (BFGS + градиент Бауером-Штрассеном). Конечно решается, но бывает, что и не сходится, или сходимость подкручивать приходится, да и уже с пол месяца на моем суперкомпьютере весит медленно решаясь.

Решая численно, заметил, что все сходится хорошо, если примерно $M < L/4$, а при $M>L/2$ гарантированно есть неустойчивость. Сам пытался как-то это учесть в теоретических выводах для уравнения-1, но пока ничего не придумал.

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

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



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

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


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

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