Линейная система с теплицевой матрицей и константной RHS

[ilghiz]

Добрый день,

есть теплицева матрица $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)$.

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

Спасибо!

[ilghiz]

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

[Евгений Машеров]

А в сторону Фурье не?

[ilghiz]

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

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

[Евгений Машеров]

А составить паровозик из вагончиков длины $2L$?

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

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

[mihiv]

Для произвольной функции $u(x)$ решения может и не быть. Пусть, например, $u(x)=e^x$, подставив в уравнение, получим противоречие:

$$e^{-y}=1,\forall y \in [-M,M]$$

[ozheredov]

ilghiz в сообщении #1439204 писал(а):

хочу решить задачу наименьших квадратов вида $\min_x ||T x - u||_2^2$, и научиться быстро выражать $x$ через первую строку и столбец этой теплицевой матрицы.

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

[svv]

Так она же тёплицева, она вся определяется первой строкой и столбцом.

[ilghiz]

Огромное спасибо за обсуждения! На самом деле у меня задача немного по-сложнее, но с частным случаем для $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$ из довольно большого диапазона найти), и уже могу не дождаться решения с той точностью, что мне надо, а с обоими условиями, пока даже еще не решился чем минимизироваться.

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

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

[DeBill]

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

[ilghiz]

Огромное спасибо, DeBill,

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

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