Clase 15: Mínimos Cuadrados¶

Bibliografía de la Clase

Numerical Linear Algebra. L.N. Trefethen. Chapter 2, Lecture 11: Least Squares Problems

Guía profesor Luis Salinas

El Problema¶

Contexto:

En algebra lineal, el problema corresponde a solucionar un sistema sobredeterminado de ecuaciones $Ax=b$ (no cuadrado) con más filas que columnas.

La idea de mínimos cuadrados es resolver este sistema minimizando la norma del resto (u error) $r=b-Ax$ .
Se desea encontrar un vector $x \in \mathbb{C}^{n}$ tal que $Ax=b$ , donde $A \in M(m\times n, \mathbb{C}), \ b \in \mathbb{C}^{n}, \ m>n$ .
En general este problema no tiene solución, dado que $b \in \mathbb{C}^{m}$ y $Col(A)$ tiene dimensión, a lo más $n \rightarrow$ se dice que el sistema está sobredeterminado.
La solución existe solamente si $b \in Col(A)$ .

Idea

Resto = $r = b- Ax \in \mathbb{C}^{m}$

Se desea obtener un $r$ lo más pequeño posible.

pequeño $\rightarrow$ tamaño $\rightarrow$ norma $|| \ ||_{2}$

Por lo tanto el problema toma la siguiente forma:

Dado $A \in M(m\times n, \mathbb{C}), m>n, b \in \mathbb{C}^{m}$ , encontrar un $x \in \mathbb{C}^{n}$ tal que $||b-Ax||_{2}$ sea mínima.

Geométricamente: Encontrar un vector $x \in \mathbb{C}^{n}$ tal que $Ax$ “sea cercano” a $b$ .

Ejemplo: Ajustes de datos polinomial¶

Se comparará la interpolación polinomial de datos, que corresponde a un sistema de ecuaciones cuadrado, con el ajuste polinomial de mediante mínimos cuadrados, el cual es un sistema rectangular.

Interpolación polinomial: Dado un conjunto de datos encontrar un polinomio que pasa exactamente por esos datos $\rightarrow$ sistema de ecuaciones cuadrado.

Si se tienen $m$ puntos distintos $x_{1}, x_{2}, \ldots, x_{m} \in \mathbb{C}$ y datos $y_{1}, y_{2}, \ldots, y_{m} \in \mathbb{C}$ , para esos puntos se debe encontrar un polinomio tal que:

$p(x_{i})=y_{i} p(x) \rightarrow \text{ polinomio interpolador es único y de grado } \leq m-1 p(x)=c_{0}+c_{1}x+ \ldots + c_{m-1}x^{m-1}, \text{ se debe cumplir: } p(x_{i})=y_{i} \ \ \forall i = 1, 2, \ldots , m$

La relación de $\{x_{i}\}, \{y_{i}\}$ con los coeficientes $\{c_{i}\} \rightarrow$ Matriz de Vandermode.

$\begin{bmatrix} 1 &x_{1} &x^{2}_{1} &\ldots &x^{m-1}_{1} \\ 1 &x_{2} &x^{2}_{2} &\ldots &x^{m-1}_{2} \\ \ldots &\ldots &\ldots &\ldots &\vdots \\ & & & \\ 1 &x_{m} &x^{2}_{m} &\ldots &x^{m-1}_{m} \end{bmatrix}$

Sistema de ecuaciones cuadrado:

$\begin{bmatrix} 1 &x_{1} &x^{2}_{1} &\ldots &x^{m-1}_{1} \\ 1 &x_{2} &x^{2}_{2} &\ldots &x^{m-1}_{2} \\ \ldots &\ldots &\ldots &\ldots &\vdots \\ & & & \\ 1 &x_{m} &x^{2}_{m} &\ldots &x^{m-1}_{m} \end{bmatrix} \begin{bmatrix} c_0 \\ c_1 \\ \vdots \\ c_{m-1}\end{bmatrix}= \begin{bmatrix} y_1 \\ y_2 \\ \vdots \\ y_m \end{bmatrix} \text{O en forma más compacta: } [x_{i}^{j}][c_{i}]=[y_{i}], \ \ 1 \leq i \leq m, \ \ 0\leq j \leq m-1$

Tiene solución si: $det[x_{i}^{j}] \neq 0$ . Este sistema si tiene solución, pero el ajuste es malo en los bordes, y el problema está mal condicionado, ya que es muy sensibles a pequeñas perturbaciones en los datos.

La figura anterior corresponde a una interpolación mediante un polinomio de grado 10 que ajusta 11 datos.

Ejercicio:

Se tienen los siguientes datos:

$\begin{tabular}{|c|c|}\hline \textbf{x} &\textbf{y}\\\hline 0 & -1 \\\hline 1 & 2 \\\hline 2 & 7 \\\hline \end{tabular}$

Construir la matriz de Vandermonde
Ajustar los datos mediante interpolación polinomial.

Ejemplo: Ajuste de Datos Polinomial mediante Mínimos Cuadrados¶

La interpolación polinomial produce oscilaciones en los bordes y es muy sensible a las perturbaciones en los datos, por lo tanto, para evitar esto se debe reducir el grado del polinomio.

$\text{ Dados } x_{1}, x_{2}, \ldots x_{m} \in \mathbb{C} \text{ e } y_{1}, y_{2}, \ldots y_{m} \in \mathbb{C}, \text{ considerar } p(x)=c_{0}+c_{1}x+ \ldots c_{n-1}x^{n-1}, \ \ n < m$

Si $p(x)$ minimiza $\sum_{i=1}^{m}|p(x_{i})-y_{i}|^{2}, p(x)$ corresponde al ajuste de datos por mínimos cuadrados.

Considerando los datos del ejercicio anterior, la siguiente figura muestra la curva obtenida mediante interpolación polinomial (azul) y mediante mínimos cuadrados (curva verde):

$\text{Interpolación Polinomial: } -1 +2x + x^2 \text{Mínimos cuadrados: } -6 + \frac{13}{2}x$

Notar que $\sum_{i=1}^{m}|p(x_{i})-y_{i}|^{2}$ es el cuadrado de la norma del resto $r \ (||r||_{2}^{2})$ para el sistema rectangular:

$\begin{bmatrix} 1 &x_{1} &x^{2}_{1} &\ldots &x^{n-1}_{1} \\ 1 &x_{2} &x^{2}_{2} &\ldots &x^{n-1}_{2} \\ \ldots &\ldots &\ldots &\ldots &\vdots \\ & & & \\ 1 &x_{m} &x^{2}_{m} &\ldots &x^{n-1}_{m} \end{bmatrix} \begin{bmatrix}c_{0} \\ c_{1} \\ \vdots \\ c_{n-1}\end{bmatrix} \approx \begin{bmatrix} y_{1} \\ y_{2} \\ \vdots \\ y_{m}\end{bmatrix} \text{ O en forma más compacta:} [x_{i}^{j}] \ [c_{j}] \approx [y_{i}] \ \ 1 \leq i \leq m \ \ \ 0 \leq \ j \leq n-1$

Ejemplo:

Polinomio de grado 7 que aproxima los 11 puntos
Menos oscilación en los bordes

Proyección Ortogonal y Ecuaciones Normales¶

Objetivo:

Encontrar el punto $Ax$ más cercano a $b$ , en el $Col(A)$ , por lo tanto, $r=b-Ax$ se minimiza.

Si $b \notin Col(A)$ , el sistema de ecuaciones $Ax=b$ no tiene solución
Por lo tanto, se busca una solución aproximada, dada por la proyección ortogonal de $b$ sobre el $Col(A)$
$y$ está dado por la proyección ortogonal de $b$ en el $Col(A)$
La proyección ortogonal $P$ que transforma $\mathbb{C}^{m}$ al $Col(A)$
En otras palabras: $r=b-Ax$ debe ser ortogonal al $Col(A)$

Teorema:

Sea $A \in M(m\times n, \mathbb{C})$ y $b \in \mathbb{C}^{m}$ . El vector $x \in \mathbb{C}^{n}$ minimiza $||r||_{2}=||b-Ax||_{2}$

$\Leftrightarrow r \perp Col(A) \ \ (a) \Leftrightarrow A^{*}r=0 \ \ (b) \Leftrightarrow A^{*}Ax=A^{*}b \ \ (c) \Leftrightarrow Pb=Ax \ \ (d)$

donde $P$ es el proyector ortogonal sobre $Col(A)$ .

El sistema de ecuaciones de $n\times n$ de (c) es conocido como ecuaciones normales, y es no singular ssi $A$ es full rank $\Rightarrow$ la solución de $x$ es única ssi $A$ tiene full rank.