New answers tagged

5

Q1: No. Here's a counter-example: >> A = eye(4)*1e-300 A = 1.0e-300 * 1.0000 0 0 0 0 1.0000 0 0 0 0 1.0000 0 0 0 0 1.0000 >> rank(A) ans = 4 >> >> rank([A, ones(4, 1)]) ans = 1 >> so, if the added column ...


1

Adding another answer to the second part of your question: "Besides a constant step size, is there an easy variable-step size I could implement and play with?" An easy way to implement some variable step size would be the following algorithm: Consider your cost function $\Phi(x)$ you would like to minimize. Choose an initial step size $\alpha$ ...


3

Suppose you want to minimize $$\Phi(x)=\frac{1}{2}||Ax-b||^2$$ The gradient is $$\frac{\partial \Phi}{\partial x} = A^T(Ax-b)$$ The step size to guarantee convergence is $$\alpha=||A^TA||^{-1}$$ Why? The direct solution to the problem is: $$x_{opt}=(A^TA)^{-1}A^Tb$$ This can be achieved iteratively if we look at the update on the estimate $x_k$. Suppose we ...


3

You lose convergence order, or in the worst case convergence altogether. You can try this out: Take $$ f(x) = \begin{cases} 0 & \text{if $x<0$} \\ x^2 & \text{if $x\ge 0$}.\end{cases} $$ The function is differentiable, but not twice differentiable at $x=0$. It's exact derivative is $f'(0)=0$. Now compute the (second-order) symmetric finite ...


2

Newton's method can refer either to a method for solving $f(x)=0$ where $f: R^{n} \rightarrow R^{n}$, or to a method for minimizing/maximizing a function $g: R^{n} \rightarrow R$ by solving the system of equations $\nabla g(x)=0$. Your function $h$ maps $R^{2}$ to $R$ and you want to find a zero of the function. This is typically done by minimizing $\min h(...


Top 50 recent answers are included