29.3: Newton multivariado

Problema con el modelo

Ahora aplicaremos el método Newton para resolver sistemas multivariados no lineales de ecuaciones. Por ejemplo, podemos considerar el sistema bivariado simple de ecuaciones no lineales\[\begin{aligned} &f_{1}\left(z_{1}, z_{2}\right)=z_{1}^{2}+2 z_{2}^{2}-22=0, \\ &f_{2}\left(z_{1}, z_{2}\right)=2 z_{1}^{2}+z_{2}^{2}-17=0 . \end{aligned}\] Tenga en cuenta que\(f_{1}\) y\(f_{2}\) son los dos paraboloides cada uno con ejes principales alineados con las direcciones de coordenadas; trazamos\(f_{1}\) y\(f_{2}\) en se muestra en Figura 29.5. Deseamos encontrar un cero\(\boldsymbol{Z}=\left(\begin{array}{ll}z_{1} & z_{2}\end{array}\right)^{\mathrm{T}}\) de\(\boldsymbol{f}(\boldsymbol{z})=\left(f_{1}\left(z_{1}, z_{2}\right) f_{2}\left(z_{1}, z_{2}\right)\right)^{\mathrm{T}}\) tal que\(\boldsymbol{f}(\boldsymbol{Z})=\overline{\mathbf{0 .} \text {. We }}\) pueda visualizar\(\boldsymbol{Z}\) como las intersecciones de las elipses\(f_{1}=0\) (la intersección de paraboloide\(f_{1}\) con el plano cero) y \(f_{2}=0\)(la intersección del paraboloide\(f_{2}\) con el plano cero). Las cuatro soluciones se\(\left(Z_{1}, Z_{2}\right)=(\pm 2, \pm 3)\) muestran como los círculos rojos en la gráfica de contorno de la Figura\(29.6\).

Método

El método de Newton para el caso multivariado sigue el mismo enfoque que para el caso univariado:

• Comience con una aproximación inicial\(\hat{z}^{0}\) de una raíz al sistema no lineal\(\boldsymbol{f}(\boldsymbol{z})=\mathbf{0}\).
• Linealizar el sistema en\(\hat{z}^{0}\) y resolver el sistema lineal resultante para obtener una mejor aproximación\(\hat{\boldsymbol{z}}^{1}\).
• Continuar linealizando y resolviendo hasta que la norma de\(\boldsymbol{f}\left(\hat{\boldsymbol{z}}^{N}\right)\) esté dentro de alguna tolerancia deseada de cero.

Sin embargo, el caso multivariado puede ser mucho más desafiante computacionalmente.

Figura 29.5: Paraboloides elípticos\(f_{1}\) y\(f_{2}\).

Figura 29.6: Gráficas de contorno de\(f_{1}\) y\(f_{2}\) con sus intersecciones de los contornos cero (las soluciones a\(\boldsymbol{f}(\boldsymbol{z})=\mathbf{0}\)) mostrados como círculos rojos.

Presentamos el método para el caso general en el que\(\boldsymbol{z}\) es un\(n\) -vector,\(\left(\begin{array}{llll}z_{1} & z_{2} & \cdots & z_{n}\end{array}\right)^{\mathrm{T}}\) y también\(\boldsymbol{f}(\boldsymbol{z})\) es un\(n\) -vector,\(\left(f_{1}(\boldsymbol{z}) \quad f_{2}(\boldsymbol{z}) \cdot f_{n}(\boldsymbol{z})\right)^{\mathrm{T}}\). Esto representa ecuaciones\(n\) no lineales en\(n\) incógnitas. (Por supuesto, aún más generalmente, podríamos considerar más ecuaciones que incógnitas o menos ecuaciones que incógnitas). Para linealizar el sistema multivariado, nuevamente utilizamos una expansión de la serie Taylor de primer orden, la cual, para una sola función multivariada linealizada en el punto\(\hat{\boldsymbol{z}}^{k}\), viene dada por\[\left.f_{\text {linear }}^{k}(\boldsymbol{z}) \equiv \frac{\partial f}{\partial z_{1}}\right|_{\hat{\boldsymbol{z}}^{k}}\left(z_{1}-\hat{z}_{1}^{k}\right)+\left.\frac{\partial f}{\partial z_{2}}\right|_{\hat{\boldsymbol{z}}^{k}}\left(z_{2}-\hat{z}_{2}^{k}\right)+\cdots+\left.\frac{\partial f}{\partial z_{n}}\right|_{\hat{\boldsymbol{z}}^{k}}\left(z_{n}-\hat{z}_{n}^{k}\right)+f\left(\hat{\boldsymbol{z}}^{k}\right)\] (cf. ecuación (29.4) en el caso univariado). Debido a que tenemos\(n\) ecuaciones en\(n\) variables, debemos linealizar cada una de las ecuaciones\(\left(\begin{array}{llll}f_{1}(\boldsymbol{z}) & f_{2}(\boldsymbol{z}) & \ldots & \left.f_{n}(\boldsymbol{z})\right)^{\mathrm{T}} \text { and then, per the Newton recipe, set }\end{array}\right.\)\(\left(f_{1}\left(\hat{\boldsymbol{z}}^{k}\right)=0 \quad \ldots \quad f_{n}\left(\hat{\boldsymbol{z}}^{k}\right)=0\right)^{\mathrm{T}}\). Nuestro sistema linealizado completo se ve como\[\begin{aligned} &\left.f_{1, \text { linear }}^{k}\left(\hat{\boldsymbol{z}}^{k+1}\right) \equiv \frac{\partial f_{1}}{\partial z_{1}}\right|_{\hat{\boldsymbol{z}}^{k}}\left(\hat{z}_{1}^{k+1}-\hat{z}_{1}^{k}\right)+\left.\frac{\partial f_{1}}{\partial z_{2}}\right|_{\hat{\boldsymbol{z}}^{k}}\left(\hat{z}_{2}^{k+1}-\hat{z}_{2}^{k}\right)+\cdots+\left.\frac{\partial f_{1}}{\partial z_{n}}\right|_{\hat{\boldsymbol{z}}^{k}}\left(\hat{z}_{n}^{k+1}-\hat{z}_{n}^{k}\right)+f_{1}\left(\hat{\boldsymbol{z}}^{k}\right)=0, \\ &\left.f_{2, \text { linear }}^{k}\left(\hat{z}^{k+1}\right) \equiv \frac{\partial f_{2}}{\partial z_{1}}\right|_{\hat{\boldsymbol{z}}^{k}}\left(\hat{z}_{1}^{k+1}-\hat{z}_{1}^{k}\right)+\left.\frac{\partial f_{2}}{\partial z_{2}}\right|_{\hat{\boldsymbol{z}}^{k}}\left(\hat{z}_{2}^{k+1}-\hat{z}_{2}^{k}\right)+\cdots+\left.\frac{\partial f_{2}}{\partial z_{n}}\right|_{\hat{\boldsymbol{z}}^{k}}\left(\hat{z}_{n}^{k+1}-\hat{z}_{n}^{k}\right)+f_{2}\left(\hat{z}^{k}\right)=0, \end{aligned}\] arriba a través de

\(\left.f_{n, \text { linear }}^{k}\left(\hat{z}^{k+1}\right) \equiv \frac{\partial f_{n}}{\partial z_{1}}\right|_{\hat{z}^{k}}\left(\hat{z}_{1}^{k+1}-\hat{z}_{1}^{k}\right)+\left.\frac{\partial f_{n}}{\partial z_{2}}\right|_{\hat{z}^{k}}\left(\hat{z}_{2}^{k+1}-\hat{z}_{2}^{k}\right)+\cdots+\left.\frac{\partial f_{n}}{\partial z_{n}}\right|_{\hat{z}^{k}}\left(\hat{z}_{n}^{k+1}-\hat{z}_{n}^{k}\right)+f_{n}\left(\hat{z}^{k}\right)=0\)

(cf. ecuación (29.5) en el caso univariado).

Podemos escribir el sistema lineal de ecuaciones (29.36) - (29.38) en forma de matriz como\[\left.f_{\text {linear }}^{k}\left(\hat{z}^{k+1}\right) \equiv\left[\begin{array}{cccc} \frac{\partial f_{1}}{\partial z_{1}} & \frac{\partial f_{1}}{\partial z_{2}} & \cdots & \frac{\partial f_{1}}{\partial z_{n}} \\ \frac{\partial f_{2}}{\partial z_{1}} & \frac{\partial f_{2}}{\partial z_{2}} & \cdots & \frac{\partial f_{2}}{\partial z_{n}} \\ \vdots & \vdots & \ddots & \vdots \\ \frac{\partial f_{n}}{\partial z_{1}} & \frac{\partial f_{n}}{\partial z_{2}} & \cdots & \frac{\partial f_{n}}{\partial z_{n}} \end{array}\right]\right|_{\hat{z}^{k}}\left[\begin{array}{c} \left(\hat{z}_{1}^{k+1}-\hat{z}_{1}^{k}\right) \\ \left(\hat{z}_{2}^{k+1}-\hat{z}_{2}^{k}\right) \\ \vdots \\ \left(\hat{z}_{n}^{k+1}-\hat{z}_{n}^{k}\right) \end{array}\right]+\left[\begin{array}{c} f_{1}\left(\hat{z}^{k}\right) \\ f_{2}\left(\hat{z}^{k}\right) \\ \vdots \\ f_{n}\left(\hat{z}^{k}\right) \end{array}\right]=\left[\begin{array}{c} 0 \\ 0 \\ \vdots \\ 0 \end{array}\right]\] o, equivalentemente,\[\boldsymbol{J}\left(\hat{\boldsymbol{z}}^{k}\right) \delta \hat{\boldsymbol{z}}^{k}=-\boldsymbol{f}\left(\hat{\boldsymbol{z}}^{k}\right) .\] Aquí la matriz\(n \times n\) jacobiana\(\boldsymbol{J}\) se define como la matriz de todas las derivadas parciales de primer orden del vector de función\(\left(\begin{array}{lllll}f_{1} & \ldots & f_{n}\end{array}\right)^{\mathrm{T}}\) con respecto al vector estado\(\left(\begin{array}{llll}z_{1} & \ldots & z_{n}\end{array}\right)^{\mathrm{T}}\):\[\boldsymbol{J}(\boldsymbol{z})=\left.\left[\begin{array}{cccc} \frac{\partial f_{1}}{\partial z_{1}} & \frac{\partial f_{1}}{\partial z_{2}} & \cdots & \frac{\partial f_{1}}{\partial z_{n}} \\ \frac{\partial f_{2}}{\partial z_{1}} & \frac{\partial f_{2}}{\partial z_{2}} & \cdots & \frac{\partial f_{2}}{\partial z_{n}} \\ \vdots & \vdots & \ddots & \vdots \\ \frac{\partial f_{n}}{\partial z_{1}} & \frac{\partial f_{n}}{\partial z_{2}} & \cdots & \frac{\partial f_{n}}{\partial z_{n}} \end{array}\right]\right|_{\boldsymbol{z}}\] tal que el\(i, j^{\text {th }}\) componente del jacobiano corresponde a la derivada parcial de la\(i^{\text {th }}\) función con respecto a la\(j^{\text {th }}\) variable,\[J_{i j}(\boldsymbol{z})=\frac{\partial f_{i}}{\partial z_{j}}(\boldsymbol{z}) .\] Así\(\boldsymbol{J}\left(\hat{\boldsymbol{z}}^{k}\right)\) denota la matriz jacobiana para el sistema evaluado en el punto\(\hat{\boldsymbol{z}}^{k}\). Tenga en cuenta también que\(\delta \hat{\boldsymbol{z}}^{k}\) es el vector de desplazamiento apuntando desde la aproximación actual\(\hat{\boldsymbol{z}}^{k}\) a la siguiente aproximación\(\hat{z}^{k+1}\)\[\delta \hat{z}^{k}=\left[\begin{array}{c} \left(\hat{z}_{1}^{k+1}-\hat{z}_{1}^{k}\right) \\ \left(\hat{z}_{2}^{k+1}-\hat{z}_{2}^{k}\right) \\ \vdots \\ \left(\hat{z}_{n}^{k+1}-\hat{z}_{n}^{k}\right) \end{array}\right] .\] Por lo tanto,\(\delta \hat{\boldsymbol{z}}^{k}\) es la actualización de Newton a nuestra iteración actual.

Ejemplo

Ahora podemos aplicar Newton para resolver el problema del\(n=2\) modelo descrito en la Sección 29.3.1: Primero\[\begin{aligned} &f_{1}\left(z_{1}, z_{2}\right)=z_{1}^{2}+2 z_{2}^{2}-22=0, \\ &f_{2}\left(z_{1}, z_{2}\right)=2 z_{1}^{2}+z_{2}^{2}-17=0 . \end{aligned}\] calculamos los elementos de la matriz jacobiana como\[J_{11}=\frac{\partial f_{1}}{\partial z_{1}}=2 z_{1}, \quad J_{12}=\frac{\partial f_{1}}{\partial z_{2}}=4 z_{2}, \quad J_{21}=\frac{\partial f_{2}}{\partial z_{1}}=4 z_{1}, \quad J_{22}=\frac{\partial f_{2}}{\partial z_{2}}=2 z_{2},\] y escribimos la matriz completa como Ahora\[\boldsymbol{J}(\boldsymbol{z})=\left[\begin{array}{ll} J_{11} & J_{12} \\ J_{21} & J_{22} \end{array}\right]=\left[\begin{array}{cc} 2 z_{1} & 4 z_{2} \\ 4 z_{1} & 2 z_{2} \end{array}\right]\] podemos realizar la iteración.

Empezamos con conjetura inicial\(\hat{\boldsymbol{z}}^{0}=\left(\begin{array}{lll}10 & 10\end{array}\right)^{\mathrm{T}}\). A continuación nos linealizamos alrededor\(\hat{\boldsymbol{z}}^{0}\) para obtener\[\boldsymbol{f}_{\text {linear }}^{0}(\boldsymbol{z}) \equiv \boldsymbol{J}\left(\hat{\boldsymbol{z}}^{0}\right)\left(\boldsymbol{z}-\hat{\boldsymbol{z}}^{0}\right)+\boldsymbol{f}\left(\hat{\boldsymbol{z}}^{0}\right)=\left[\begin{array}{cc} 20 & 40 \\ 40 & 20 \end{array}\right] \delta \hat{\boldsymbol{z}}^{0}+\left[\begin{array}{l} 278 \\ 283 \end{array}\right]\] Tenga en cuenta que podemos visualizar este sistema como dos planos tangentes a\(f_{1}\) y\(f_{2}\) en\(\hat{\boldsymbol{z}}^{0}\). Ahora resolvemos el sistema linealizado\[\boldsymbol{f}_{\text {linear }}^{0}\left(\hat{\boldsymbol{z}}^{1}\right) \equiv\left[\begin{array}{cc} 20 & 40 \\ 40 & 20 \end{array}\right] \delta \hat{\boldsymbol{z}}^{0}+\left[\begin{array}{c} 278 \\ 283 \end{array}\right]=\left[\begin{array}{l} 0 \\ 0 \end{array}\right]\] o\[\left[\begin{array}{cc} 20 & 40 \\ 40 & 20 \end{array}\right] \delta \boldsymbol{z}^{0}=\left[\begin{array}{c} -278 \\ -283 \end{array}\right]\] para encontrar\[\delta \hat{\boldsymbol{z}}^{0}=\left[\begin{array}{c} -4.8 \\ -4.55 \end{array}\right]\] así la siguiente aproximación para la raíz de\(\boldsymbol{f}(z)\) es dada por\[\hat{\boldsymbol{z}}^{1}=\hat{\boldsymbol{z}}^{0}+\delta \hat{\boldsymbol{z}}^{0}=\left[\begin{array}{l} 5.2 \\ 5.45 \end{array}\right] .\] Repetimos el procedimiento para encontrar

Vemos que la solución se acerca rápidamente a la (más cercana) solución exacta\(\boldsymbol{Z}=\left(\begin{array}{ll}2 & 3\end{array}\right)^{\mathrm{T}}\).

Algorithm

El algoritmo multivariado de Newton es idéntico al algoritmo univariado, excepto que ahora para cada paso a través del bucle while ahora debemos resolver un sistema linealizado de ecuaciones que involucra a la matriz jacobiana.

Podemos ver que el costo computacional para la iteración multivariada de Newton es esencialmente el número total de iteraciones multiplicado por el costo para resolver un sistema\(n \times n\) lineal -que, si es denso,\[\begin{aligned} & \boldsymbol{f}_{\text {linear }}^{1}(\boldsymbol{z}) \equiv \boldsymbol{J}\left(\hat{\boldsymbol{z}}^{1}\right)\left(\boldsymbol{z}-\hat{\boldsymbol{z}}^{1}\right)+\boldsymbol{f}\left(\hat{\boldsymbol{z}}^{1}\right)=\left[\begin{array}{cc}10.4 & 21.8 \\20.8 & 10.9\end{array}\right] \delta \hat{\boldsymbol{z}}^{1}+\left[\begin{array}{c}64.445 \\66.7825\end{array}\right], \\ & \boldsymbol{f}_{\text {linear }}^{1}\left(\hat{\boldsymbol{z}}^{2}\right)=\mathbf{0} \\ & \hat{\boldsymbol{z}}^{2}=\left[\begin{array}{c}2.9846 \\3.5507\end{array}\right] ; \\ & \boldsymbol{f}_{\text {linear }}^{2}(\boldsymbol{z})=\equiv \boldsymbol{J}\left(\hat{\boldsymbol{z}}^{2}\right)\left(\boldsymbol{z}-\hat{\boldsymbol{z}}^{2}\right)+\boldsymbol{f}\left(\hat{\boldsymbol{z}}^{2}\right)=\left[\begin{array}{cc}5.9692 & 14.2028 \\11.9385 & 7.1014\end{array}\right] \delta \hat{\boldsymbol{z}}^{2}+\left[\begin{array}{l}12.1227 \\13.4232\end{array}\right] \text {, } \\ & \boldsymbol{f}_{\text {linear }}^{2}\left(\hat{\boldsymbol{z}}^{3}\right)=\mathbf{0} \\ & \hat{\boldsymbol{z}}^{3}=\left[\begin{array}{l}2.1624 \\3.0427\end{array}\right] . \end{aligned}\] podría ser tanto como\(\mathcal{O}\left(n^{3}\right)\) y, si escaso, tan poco como \(\mathcal{O}(n)\)operaciones. Adicionalmente, para Newton “puro”, el jacobiano necesita ser recalculado\(\left(\mathcal{O}\left(n^{2}\right)\right.\) operaciones) en cada iteración. (En Newton “impuro” el jacobiano a veces se mantiene fijo durante varias iteraciones o se actualiza selectivamente).

Tenga en cuenta que, como antes en el caso univariado, podemos sustituir una aproximación de diferencia finita por el jacobiano si no podemos (o elegir no) utilizar las expresiones analíticas. Aquí primero introducimos un escalar\(\Delta z\) (pequeño); nota que no\(\Delta z\) está relacionado con\(\delta \boldsymbol{z}\) - es decir, este no es un enfoque secante. Luego aproximamos, para\(1 \leq i \leq n, 1 \leq j \leq n\),\[J_{i j}(\boldsymbol{z}) \equiv \frac{\partial f_{i}}{\partial z_{j}}(\boldsymbol{z}) \approx \frac{f_{i}\left(\boldsymbol{z}+\Delta z \boldsymbol{e}^{j}\right)-f_{i}(\boldsymbol{z})}{\Delta z} \equiv \widetilde{J}_{i j}(\boldsymbol{z}),\] donde\(e^{j}\) está el vector unitario en la\(j\) -dirección tal que\(z+\Delta z e^{j}\) difiere de solo\(z\) en el\(j^{\text {th }}\) componente - una diferencia parcial aproximación a la derivada parcial\(\frac{\partial f_{i}}{\partial z_{j}}\). Tenga en cuenta que para calcular la\(n \times n\) matriz de aproximación de diferencia finita completa\(\widetilde{\boldsymbol{J}}(\boldsymbol{z})\) necesitamos evaluaciones de\(\mathcal{O}\left(n^{2}\right)\) funciones.

Comentarios en Multivariate Newton

Para Newton multivariado, tanto la tasa de convergencia como las patologías son similares al caso univariado, aunque las patologías son algo más probables en el caso multivariado dado el mayor número de grados de libertad.

La principal diferencia para el caso multivariado, entonces, es el costo relativo de cada iteración de Newton (\(\mathcal{O}\left(n^{3}\right)\)operaciones en el peor de los casos) debido al tamaño del sistema lineal que debe resolverse. Por esta razón, la rápida convergencia de Newton se vuelve más crucial con la creciente dimensionalidad. Gracias a la rápida convergencia, Newton a menudo supera a los enfoques “más simples” que son menos costosos computacionalmente por iteración pero requieren muchas más iteraciones para converger en una solución.