#LyX 2.3 created this file. For more info see http://www.lyx.org/ \lyxformat 544 \begin_document \begin_header \save_transient_properties true \origin unavailable \textclass book \begin_preamble \input{../defs} \end_preamble \use_default_options true \begin_modules algorithm2e \end_modules \maintain_unincluded_children false \language spanish \language_package default \inputencoding auto \fontencoding global \font_roman "default" "default" \font_sans "default" "default" \font_typewriter "default" "default" \font_math "auto" "auto" \font_default_family default \use_non_tex_fonts false \font_sc false \font_osf false \font_sf_scale 100 100 \font_tt_scale 100 100 \use_microtype false \use_dash_ligatures true \graphics default \default_output_format default \output_sync 0 \bibtex_command default \index_command default \paperfontsize default \spacing single \use_hyperref false \papersize default \use_geometry false \use_package amsmath 1 \use_package amssymb 1 \use_package cancel 1 \use_package esint 1 \use_package mathdots 1 \use_package mathtools 1 \use_package mhchem 1 \use_package stackrel 1 \use_package stmaryrd 1 \use_package undertilde 1 \cite_engine basic \cite_engine_type default \biblio_style plain \use_bibtopic false \use_indices false \paperorientation portrait \suppress_date false \justification true \use_refstyle 1 \use_minted 0 \index Index \shortcut idx \color #008000 \end_index \secnumdepth 3 \tocdepth 3 \paragraph_separation indent \paragraph_indentation default \is_math_indent 0 \math_numbering_side default \quotes_style french \dynamic_quotes 0 \papercolumns 1 \papersides 1 \paperpagestyle default \tracking_changes false \output_changes false \html_math_output 0 \html_css_as_file 0 \html_be_strict false \end_header \begin_body \begin_layout Standard Sean \begin_inset Formula $A\in{\cal M}_{m\times n}(\mathbb{C})$ \end_inset y \begin_inset Formula $b\in\mathbb{C}^{m}$ \end_inset , un \series bold método iterativo de resolución \series default del sistema lineal \begin_inset Formula $Ax=b$ \end_inset es un par \begin_inset Formula $(T,c)$ \end_inset con \begin_inset Formula $T\in{\cal M}_{n}$ \end_inset y \begin_inset Formula $c\in\mathbb{C}^{n}$ \end_inset tal que la solución del sistema es el único punto fijo de \begin_inset Formula $\Phi(x)\coloneqq Tx+c$ \end_inset . Si para todo \begin_inset Formula $x\in\mathbb{C}^{n}$ \end_inset la sucesión \begin_inset Formula $(x_{n})_{n}$ \end_inset dada por \begin_inset Formula $x_{0}\coloneqq x$ \end_inset y \begin_inset Formula $x_{k+1}\coloneqq\Phi(x_{k})$ \end_inset converge hacia el punto fijo, \begin_inset Formula $(T,c)$ \end_inset es \series bold convergente \series default . \end_layout \begin_layout Standard Sea \begin_inset Formula $T\in{\cal M}_{n}$ \end_inset , \begin_inset Formula $\rho(T)<1$ \end_inset si y sólo si, para cualesquiera \begin_inset Formula $c,y\in\mathbb{C}^{n}$ \end_inset , la sucesión \begin_inset Formula $x_{0}\coloneqq y$ \end_inset , \begin_inset Formula $x_{k+1}\coloneqq Tx_{k}+c$ \end_inset , converge. \end_layout \begin_layout Itemize \begin_inset Argument item:1 status open \begin_layout Plain Layout \begin_inset Formula $\implies]$ \end_inset \end_layout \end_inset Entonces existe una norma matricial tal que \begin_inset Formula $\Vert T\Vert<1$ \end_inset , y si \begin_inset Formula $\Phi(x)\coloneqq Tx+c$ \end_inset , \begin_inset Formula $\Vert\Phi(x)-\Phi(y)\Vert=\Vert Tx-Ty\Vert=\Vert T(x-y)\Vert\leq\Vert T\Vert\Vert x-y\Vert$ \end_inset , luego \begin_inset Formula $\Phi$ \end_inset es contractiva y, por el teorema del punto fijo de Banach, la sucesión converge a un punto fijo. \end_layout \begin_layout Itemize \begin_inset Argument item:1 status open \begin_layout Plain Layout \begin_inset Formula $\impliedby]$ \end_inset \end_layout \end_inset Sean \begin_inset Formula $c,v\in\mathbb{C}^{n}$ \end_inset , \begin_inset Formula $x$ \end_inset la solución de \begin_inset Formula $x=Tx+c$ \end_inset , \begin_inset Formula $y\coloneqq x-v$ \end_inset y \begin_inset Formula $(x_{n})_{n}$ \end_inset la sucesión del enunciado, entonces \begin_inset Formula $x-x_{0}=v=T^{0}v$ \end_inset , y si \begin_inset Formula $x-x_{k}=T^{k}v$ \end_inset , entonces \begin_inset Formula $x-x_{k+1}=(Tx+c)-(Tx_{k}+c)=T(x-x_{k})=TT^{k}v=T^{k+1}v$ \end_inset . Por tanto \begin_inset Formula $\lim_{k}T^{k}v=\lim_{k}(x-x_{k})=0$ \end_inset , y que esto ocurra para \begin_inset Formula $v$ \end_inset arbitrario equivale a que \begin_inset Formula $\rho(T)<1$ \end_inset . \end_layout \begin_layout Standard Dado un sistema lineal \begin_inset Formula $Ax=b$ \end_inset , si \begin_inset Formula $A=M-N$ \end_inset con \begin_inset Formula $M$ \end_inset fácil de invertir, entonces \begin_inset Formula $(M^{-1}N,M^{-1}b)$ \end_inset es un método iterativo de resolución de \begin_inset Formula $Ax=b$ \end_inset , pues \begin_inset Formula $Ax=Mx-Nx=b\iff Mx=Nx+b\iff x=M^{-1}Nx+M^{-1}b$ \end_inset . El \series bold método iterativo de Richardson \series default para una matriz \begin_inset Formula $A\coloneqq(a_{ij})$ \end_inset sin ceros en la diagonal consiste en tomar como matriz fácil de invertir en lo anterior una matriz \begin_inset Formula $\alpha I_{n}$ \end_inset para un cierto \begin_inset Formula $\alpha\in\mathbb{C}$ \end_inset . \end_layout \begin_layout Section Método de Jacobi \end_layout \begin_layout Standard En adelante, \begin_inset Formula $Ax=b$ \end_inset es un sistema lineal tal que \begin_inset Formula $A$ \end_inset no tiene ceros en la diagonal, \begin_inset Formula $D$ \end_inset es la matriz diagonal de \begin_inset Formula $A$ \end_inset , \begin_inset Formula $L$ \end_inset la matriz formada por los elementos de \begin_inset Formula $A$ \end_inset bajo la diagonal y \begin_inset Formula $U$ \end_inset la formada por los elementos sobre la diagonal, de modo que \begin_inset Formula $A=L+D+U$ \end_inset . \end_layout \begin_layout Standard Para el método de Jacobi tomamos \begin_inset Formula $M\coloneqq D$ \end_inset y \begin_inset Formula $N\coloneqq-(L+U)$ \end_inset , y nos queda el método iterativo \begin_inset Formula $(T_{J}\coloneqq-D^{-1}(L+U),D^{-1}b)$ \end_inset . \end_layout \begin_layout Standard Para calcular de forma eficiente, en cada iteración calculamos \begin_inset Formula $r_{k}\coloneqq Ax_{k}-b$ \end_inset y \begin_inset Formula $x_{k+1}=x_{k}-D^{-1}r_{k}$ \end_inset , pues \begin_inset Formula $D^{-1}r_{k}=D^{-1}(Dx_{k}+(L+U)x_{k}-b)=x_{k}-(-D^{-1}(L+U)x_{k}+D^{-1}b)=x_{k}-x_{k+1}$ \end_inset . \end_layout \begin_layout Section Método de Gauss-Seidel \end_layout \begin_layout Standard Es como el de Jacobi pero, para calcular una coordenada de \begin_inset Formula $x_{k+1}$ \end_inset , usamos las coordenadas anteriores, que ya habremos calculado, en vez de las correspondientes de \begin_inset Formula $x_{k}$ \end_inset , pues serán una mejor aproximación. Si \begin_inset Formula $A\in{\cal M}_{n}$ \end_inset , para \begin_inset Formula $i$ \end_inset de 1 a \begin_inset Formula $n$ \end_inset , calculamos \begin_inset Formula \[ \tilde{r}_{ki}:=\sum_{j=1}^{i-1}a_{ij}x_{(k+1)j}+\sum_{j=i}^{n}a_{ij}x_{kj}-b_{i} \] \end_inset y \begin_inset Formula \[ x_{(k+1)i}:=x_{ki}-\frac{\tilde{r}_{ki}}{a_{ii}}=\frac{1}{a_{ii}}\left(b_{i}-\sum_{j=1}^{i-1}a_{ij}x_{(k+1)j}-\sum_{j=i+1}^{n}a_{ij}x_{kj}\right). \] \end_inset Esto es el método \begin_inset Formula $(T_{G}\coloneqq-(L+D)^{-1}U,(L+D)^{-1}b)$ \end_inset , equivalente a tomar \begin_inset Formula $M\coloneqq L+D$ \end_inset y \begin_inset Formula $N\coloneqq-U$ \end_inset . \series bold Demostración: \series default Despejando, \begin_inset Formula \[ a_{ii}x_{(k+1)i}+\sum_{j=1}^{i-1}a_{ij}x_{(k+1)j}=b_{i}-\sum_{j=i+1}^{n}a_{ij}x_{kj}, \] \end_inset esto es, \begin_inset Formula $((L+D)x_{k+1})_{i}=b_{i}-(Ux_{k})_{i}$ \end_inset , luego \begin_inset Formula $(L+D)x_{k+1}=b-Ux_{k}$ \end_inset . \end_layout \begin_layout Standard Tenemos que \begin_inset Formula $\tilde{r}_{ki}=A\tilde{x}_{ki}-b$ \end_inset , donde \begin_inset Formula $\tilde{x}_{ki}=(x_{(k+1)1},\dots,x_{(k+1)(i-1)},x_{ki},\dots,x_{kn})$ \end_inset , por lo que podemos usar como condición de parada que \begin_inset Formula $\tilde{r}_{k}$ \end_inset sea lo suficientemente pequeño. \end_layout \begin_layout Standard \series bold Teorema de P. Stein y R. L. Rosenberg \series default (1948) \series bold : \series default Si \begin_inset Formula $A=D+L+U\in{\cal M}_{n}(\mathbb{R})$ \end_inset con \begin_inset Formula $L,U\leq0$ \end_inset , \begin_inset Formula $L,U\neq0$ \end_inset y \begin_inset Formula $L$ \end_inset y \begin_inset Formula $U$ \end_inset triangulares estrictamente inferior y superior, respectivamente, se da exactamente una de las siguientes afirmaciones: \end_layout \begin_layout Enumerate \begin_inset Formula $0\leq\rho(T_{G})\leq\rho(T_{J})<1$ \end_inset . \end_layout \begin_layout Enumerate \begin_inset Formula $\rho(T_{J})=\rho(T_{G})=1$ \end_inset . \end_layout \begin_layout Enumerate \begin_inset Formula $1<\rho(T_{J})\leq\rho(T_{G})$ \end_inset . \end_layout \begin_layout Standard Por tanto, si el método de Jacobi converge, el de Gauss-Seidel lo hace más rápido, y si diverge, también. \end_layout \begin_layout Standard Si \begin_inset Formula $A\in{\cal M}_{n}(\mathbb{R})$ \end_inset tiene diagonal estrictamente dominante, los métodos de Jacobi y Gauss-Seidel para resolver \begin_inset Formula $Ax=b$ \end_inset convergen y \begin_inset Formula $\Vert T_{G}\Vert_{\infty}\leq\Vert T_{J}\Vert_{\infty}<1$ \end_inset . \series bold Demostración: \series default \begin_inset Formula $(T_{J})_{ij}=-(1-\delta_{ij})\frac{a_{ij}}{a_{ii}}$ \end_inset , luego \begin_inset Formula $\Vert T_{J}\Vert_{\infty}=\max_{i}\sum_{j}|(T_{J})_{ij}|=\max_{i}\sum_{j\neq i}\frac{|a_{ij}|}{|a_{ii}|}<1$ \end_inset y \begin_inset Formula $\rho(T_{J})<1$ \end_inset . Sean \begin_inset Formula $y\in\mathbb{R}^{n}$ \end_inset y \begin_inset Formula $z\coloneqq T_{G}y$ \end_inset , con lo que \begin_inset Formula $(L+D)z=-Uy$ \end_inset , y queremos ver que, para \begin_inset Formula $i\in\{1,\dots,n\}$ \end_inset , \begin_inset Formula $|z_{i}|\leq\frac{1}{|a_{ii}|}\sum_{j\neq i}|a_{ij}|\Vert y\Vert_{\infty}$ \end_inset , y en particular \begin_inset Formula $|z_{i}|\leq\Vert T_{J}\Vert_{\infty}\Vert y\Vert_{\infty}$ \end_inset . Para \begin_inset Formula $i=1$ \end_inset , \begin_inset Formula \[ |a_{11}||z_{1}|=|(L+D)_{11}z_{1}|=|((L+D)z)_{1}|=|-Uy|=\left|\sum_{j=2}^{n}a_{1j}y_{j}\right|\leq\sum_{j=2}^{n}|a_{1j}||y_{j}|\leq\sum_{j=2}^{n}|a_{1j}|\Vert y\Vert_{\infty}. \] \end_inset Para \begin_inset Formula $i>1$ \end_inset , usando la fórmula con \begin_inset Formula $b=0$ \end_inset , \begin_inset Formula \begin{eqnarray*} |z_{i}| & = & \left|\frac{1}{a_{ii}}\left(-\sum_{j=1}^{i-1}a_{ij}z_{j}-\sum_{j=i+1}^{n}a_{ij}y_{j}\right)\right|\leq\frac{1}{|a_{ii}|}\left(\sum_{j=1}^{i-1}|a_{ij}||z_{j}|+\sum_{i=j+1}^{n}|a_{ij}||y_{j}|\right)\\ & \leq & \frac{1}{|a_{ij}|}\left(\sum_{j=1}^{i-1}|a_{ij}|\Vert T_{J}\Vert_{\infty}+\sum_{j=1}^{i-1}|a_{ij}|\right)\Vert y\Vert_{\infty}\overset{\Vert T_{J}\Vert_{\infty}<1}{\leq}\frac{1}{|a_{ij}|}\sum_{j\neq i}|a_{ij}|\Vert y\Vert_{\infty}. \end{eqnarray*} \end_inset Por tanto \begin_inset Formula $\Vert T_{G}y\Vert_{\infty}=\Vert z\Vert_{\infty}\leq\Vert T_{J}\Vert_{\infty}\Vert y\Vert_{\infty}$ \end_inset y, tomando \begin_inset Formula $y\coloneqq(1,\dots,1)_{\infty}$ \end_inset , \begin_inset Formula $\Vert T_{G}\Vert_{\infty}=\max_{i}\sum_{j}|(T_{G})_{ij}||y_{j}|=\Vert T_{G}y\Vert_{\infty}\leq\Vert T_{J}\Vert_{\infty}\Vert y\Vert_{\infty}=\Vert T_{J}\Vert_{\infty}$ \end_inset . \end_layout \begin_layout Standard Si \begin_inset Formula $A$ \end_inset es tridiagonal es \begin_inset Formula $\rho(T_{G})=\rho(T_{J})^{2}$ \end_inset , con lo que los métodos de Jacobi y Gauss-Seidel convergen simultáneamente y, entonces, el de Gauss-Seidel converge más rápido. \series bold Demostración: \series default Vemos primero que si \begin_inset Formula $A:\mathbb{C}\to{\cal M}_{n}(\mathbb{C})$ \end_inset es de la forma \begin_inset Formula \[ A(\lambda):=\left(\begin{array}{ccccc} \lambda b_{1} & c_{1}\\ \lambda^{2}a_{2} & \lambda b_{2} & c_{2}\\ & \ddots & \ddots & \ddots\\ & & \lambda^{2}a_{n-1} & \lambda b_{n-1} & c_{n-1}\\ & & & \lambda^{2}a_{n} & \lambda b_{n} \end{array}\right), \] \end_inset entonces \begin_inset Formula $\det(A(\lambda))=\det(A(1))$ \end_inset para todo \begin_inset Formula $\lambda\neq0$ \end_inset . En efecto, sea \begin_inset Formula $Q(\lambda)\coloneqq\text{diag}(\lambda,\lambda^{2},\dots,\lambda^{n})$ \end_inset , es fácil ver que \begin_inset Formula $A(\lambda)=Q(\lambda)A(1)Q(\lambda)^{-1}$ \end_inset . Los valores propios de \begin_inset Formula $T_{J}$ \end_inset son los ceros de \begin_inset Formula $p_{J}(\lambda)\coloneqq\det(-D^{-1}(L+U)-\lambda I_{n})$ \end_inset , que son los mismos que los de \begin_inset Formula $q_{J}(\lambda)\coloneqq\det(L+U+\lambda D)$ \end_inset . Los de \begin_inset Formula $T_{G}$ \end_inset son los ceros de \begin_inset Formula $p_{G}(\lambda)\coloneqq\det(-(L+D)^{-1}U-\lambda I_{n})$ \end_inset , que son los de \begin_inset Formula $q_{G}(\lambda)\coloneqq\det(U+\lambda L+\lambda D)$ \end_inset . Usando el resultado al principio, para \begin_inset Formula $\lambda\neq0$ \end_inset , \begin_inset Formula $q_{G}(\lambda^{2})=\det(\lambda^{2}D+\lambda^{2}L+U)=\det(\lambda^{2}L+\lambda(\lambda D)+U)=\det(L+\lambda D+U)=q_{J}(\lambda)$ \end_inset , y para \begin_inset Formula $\lambda=0$ \end_inset esto se cumple por continuidad. Así, \begin_inset Formula $\lambda$ \end_inset es valor propio de \begin_inset Formula $T_{J}$ \end_inset si y sólo si \begin_inset Formula $\lambda^{2}$ \end_inset lo es de \begin_inset Formula $T_{G}$ \end_inset , de donde se obtiene el resultado. \end_layout \begin_layout Section Método de relajación \end_layout \begin_layout Standard Se trata de encontrar un peso \begin_inset Formula $\omega>0$ \end_inset para corregir las coordenadas de \begin_inset Formula $x_{k}$ \end_inset poniendo \begin_inset Formula \[ x_{(k+1)i}:=x_{ki}-\frac{\omega}{a_{ii}}\tilde{r}_{ki} \] \end_inset en el método de Gauss-Seidel. Entonces el método es \begin_inset Formula $(T_{R}(\omega)\coloneqq(D+\omega L)^{-1}((1-\omega)D-\omega U),(D+\omega L)^{-1}\omega)$ \end_inset , que equivale a tomar \begin_inset Formula $M\coloneqq\frac{1}{\omega}D+L$ \end_inset y \begin_inset Formula $N\coloneqq\frac{1-\omega}{\omega}D-U$ \end_inset . \series bold Demostración: \series default Ahora es \begin_inset Formula \[ a_{ii}x_{(k+1)i}=a_{ii}x_{ki}-\omega\left(\sum_{j=1}^{i-1}a_{ij}x_{(k+1)j}+\sum_{j=i}^{n}a_{ij}x_{kj}-b_{i}\right), \] \end_inset luego \begin_inset Formula \[ a_{ii}x_{(k+1)i}+\omega\sum_{j=1}^{i-1}a_{ij}x_{(k+1)j}=(1-\omega)a_{ii}x_{ki}-\omega\sum_{j=i+1}^{n}a_{ij}x_{kj}-b_{i}, \] \end_inset con lo que \begin_inset Formula $(D+\omega L)x_{k+1}=(1-\omega)D-\omega U-b$ \end_inset . Entonces, \begin_inset Formula $(D+\omega L)^{-1}((1-\omega)D+\omega U)=(\frac{1}{\omega}D+\omega L)^{-1}(\frac{1-\omega}{\omega D}+U)$ \end_inset . \end_layout \begin_layout Standard \series bold Teorema de Kahan \series default (1958) \series bold : \series default \begin_inset Formula $\rho(T_{R}(\omega))>|\omega-1|$ \end_inset , y en particular el método de relajación solo puede ser convergente para \begin_inset Formula $\omega\in(0,2)$ \end_inset . \series bold Demostración: \series default \begin_inset Formula \[ \det T_{R}(\omega)=\frac{\det((1-\omega)D-\omega U)}{\det(D+\omega L)}=\frac{\det((1-\omega)D)}{\det(D)}=(1-\omega)^{n}, \] \end_inset con lo que si \begin_inset Formula $\lambda_{1},\dots,\lambda_{n}$ \end_inset son los valores propios de \begin_inset Formula $T_{R}(\omega)$ \end_inset , repetidos según sea su multiplicidad, \begin_inset Formula $\rho(T_{R}(\omega))^{n}\geq\prod_{k=1}^{n}|\lambda_{k}|=|\det T_{R}(\omega)|=|1-\omega|^{n}$ \end_inset . \end_layout \begin_layout Standard Si \begin_inset Formula $A$ \end_inset es SPD, el método de relajación converge para \begin_inset Formula $\omega\in(0,2)$ \end_inset . \series bold Demostración: \series default Si \begin_inset Formula $M\coloneqq\frac{1}{\omega}D+L$ \end_inset y \begin_inset Formula $N\coloneqq\frac{1-\omega}{\omega}D-U$ \end_inset , \begin_inset Formula $A=M-N$ \end_inset y \begin_inset Formula $T_{R}(\omega)=M^{-1}N$ \end_inset . Además, como \begin_inset Formula $L^{t}=U$ \end_inset , \begin_inset Formula $M^{t}+N=\frac{2-\omega}{\omega}D$ \end_inset , que es SPD, y queremos ver que entonces \begin_inset Formula $\rho(M^{-1}N)\leq\Vert M^{-1}N\Vert_{A}<1$ \end_inset . En dimensión finita, \begin_inset Formula $\Vert M^{-1}N\Vert_{A}=\max\{\Vert M^{-1}Nv\Vert_{A}\mid\Vert v\Vert_{A}=1\}$ \end_inset . Sean \begin_inset Formula $v\in\mathbb{R}^{n}$ \end_inset con \begin_inset Formula $\Vert v\Vert_{A}^{2}=1$ \end_inset tal que \begin_inset Formula $\Vert M^{-1}N\Vert_{A}=\Vert M^{-1}Nv\Vert_{A}$ \end_inset y \begin_inset Formula $w\coloneqq M^{-1}Av$ \end_inset , entonces \begin_inset Formula $Mw=Av$ \end_inset , luego \begin_inset Formula \begin{align*} \Vert M^{-1}Nv\Vert_{A}^{2} & =\langle AM^{-1}Nv,M^{-1}Nv\rangle=\langle AM^{-1}(M-A)v,M^{-1}(M-A)v\rangle=\\ & =\langle Av-AM^{-1}Av,v-M^{-1}Av\rangle=\\ & =\langle Av,v\rangle-\langle AM^{-1}Av,v\rangle-\langle Av,M^{-1}Av\rangle+\langle AM^{-1}Av,M^{-1}Av\rangle=\\ & =1-\langle M^{-1}Av,Av\rangle-\langle Mw,w\rangle+\langle Aw,w\rangle=\\ & =1-\langle w,Mw\rangle-\langle Mw,w\rangle+\langle(M-N)w,w\rangle=1-\langle M^{t}w,w\rangle-\langle Nw,w\rangle=\\ & =1-\langle(M^{t}+N)w,w\rangle<1, \end{align*} \end_inset por ser \begin_inset Formula $M^{t}+N$ \end_inset definida positiva. \end_layout \begin_layout Standard Si \begin_inset Formula $A$ \end_inset es SPD y tridiagonal, los métodos de Jacobi, Gauss-Seidel y relajación para \begin_inset Formula $0<\omega<2$ \end_inset convergen. Además, el mínimo \begin_inset Formula $\rho(T_{R}(\omega))$ \end_inset para \begin_inset Formula $\omega\in(0,2)$ \end_inset se alcanza en \begin_inset Formula \[ \omega=\omega_{0}:=\frac{2}{1+\sqrt{1-\rho(T_{J})^{2}}}, \] \end_inset con lo que \begin_inset Formula $\rho(T_{R}(\omega_{0}))\leq\rho(T_{G})<\rho(T_{J})$ \end_inset , y se tiene \begin_inset Formula $\rho(T_{R}(\omega_{0}))=\omega_{0}-1$ \end_inset . \end_layout \begin_layout Section Método del descenso rápido \end_layout \begin_layout Standard Si \begin_inset Formula $A$ \end_inset es SPD, \begin_inset Formula $x\in\mathbb{R}^{n}$ \end_inset es solución de \begin_inset Formula $Ax=b$ \end_inset si y sólo si minimiza \begin_inset Formula $g(x)\coloneqq x^{t}Ax-2x^{t}b$ \end_inset , y para \begin_inset Formula $v\in\mathbb{R}^{n}\setminus0$ \end_inset , el mínimo de \begin_inset Formula $h(t)\coloneqq g(x+tv)$ \end_inset es \begin_inset Formula $\frac{v^{t}(b-Ax)}{v^{t}Av}$ \end_inset . \series bold Demostración: \series default Sean \begin_inset Formula $v\in\mathbb{R}^{n}\setminus\{0\}$ \end_inset y \begin_inset Formula $t\in\mathbb{R}$ \end_inset , \begin_inset Formula \begin{multline*} g(x+tv)=(x+tv)^{t}A(x+tv)-2(x+tv)^{t}b=\\ =x^{t}Ax+tv^{t}Ax+tx^{t}Av+t^{2}v^{t}Av-2x^{t}b-2tv^{t}b=g(x)-2tv^{t}(b-Ax)+t^{2}v^{t}Av, \end{multline*} \end_inset luego el mínimo de \begin_inset Formula $h$ \end_inset es \begin_inset Formula $t_{xv}$ \end_inset tal que \begin_inset Formula $h'(t_{xv})=2t_{xv}v^{t}Av-2v^{t}(b-Ax)=0\iff t_{xv}=\frac{v^{t}(b-Ax)}{v^{t}Av}$ \end_inset . En efecto, \begin_inset Formula $h''(t_{xv})=2v^{t}Av>0$ \end_inset . Así: \end_layout \begin_layout Itemize \begin_inset Argument item:1 status open \begin_layout Plain Layout \begin_inset Formula $\implies]$ \end_inset \end_layout \end_inset Si \begin_inset Formula $Ax=b$ \end_inset , \begin_inset Formula $b-Ax=0$ \end_inset y \begin_inset Formula $t_{xv}=0$ \end_inset para todo \begin_inset Formula $v\neq0$ \end_inset , luego \begin_inset Formula $x$ \end_inset es el mínimo de \begin_inset Formula $g$ \end_inset en cualquier dirección. \end_layout \begin_layout Itemize \begin_inset Argument item:1 status open \begin_layout Plain Layout \begin_inset Formula $\impliedby]$ \end_inset \end_layout \end_inset Si \begin_inset Formula $x$ \end_inset minimiza \begin_inset Formula $g$ \end_inset , para cualquier dirección \begin_inset Formula $v\neq0$ \end_inset , \begin_inset Formula $t_{xv}=0$ \end_inset , luego \begin_inset Formula $v^{t}(b-Ax)=0$ \end_inset y, en particular, \begin_inset Formula $\Vert b-Ax\Vert=0$ \end_inset y \begin_inset Formula $Ax=b$ \end_inset . \end_layout \begin_layout Standard El vector gradiente \begin_inset Formula \[ \nabla g(x)=\left(\frac{\partial g}{\partial x_{1}}(x),\dots,\frac{\partial g}{\partial x_{n}}(x)\right) \] \end_inset es el de máximo crecimiento en \begin_inset Formula $x$ \end_inset , y el \series bold método del descenso rápido \series default consiste en partir de un \begin_inset Formula $x_{0}$ \end_inset y hacer \begin_inset Formula $x_{k+1}\coloneqq x_{k}-\alpha\nabla g(x_{k})$ \end_inset , donde \begin_inset Formula $\alpha$ \end_inset minimiza \begin_inset Formula $g(x_{k+1})$ \end_inset . Se tiene \begin_inset Formula $\nabla g(x)=2(Ax-b)$ \end_inset . \series bold Demostración: \series default \begin_inset Formula $g(x)=\sum_{k=1}^{n}a_{kk}x_{k}^{2}+2\sum_{1\leq i