Hot answers tagged

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(...


2

If a certain velocity component is periodic with period $\tau$ that means that the corresponding coordinate, as a function of time, is a sum of a linear function and a periodic function with the same period. To prove it, let $\dot{x}(t)$ be periodic, $\dot{x}(t+\tau)=\dot{x}(t)$, and the integral over the period $\int_{t}^{t+\tau} \dot{x} dt = I$, where $I$ ...


2

Think of an object that moves along a spiral -- say, an electron moving in a uniform magnetic field. Its positions are not periodic (it never comes back to its original place) but its velocities are. Looking at periodicity in the velocities therefore tells us something we don't know by just looking at the positions.


2

One way to approach this is to use some adaptive scheme for your timestepping. If you have a fixed timestep width, it can happen that two of your particles switch positions (as you said). If you build a mechanism into your algorithm that reduces the time-step $h$ whenever two particles get too close to each other $|f_i(x) - f_{i+1}(x)|<\epsilon$, then ...


2

The asymptotic order of convergence of Brent's method tends to be either 1.618 and 1.689, of which the Alefeld-Potra-Shi's methods lie directly in between. The main difference of the Alefeld-Potra-Shi's methods are the tightness of the bounds, which Brent's method may fail to give during intermediate iterations. Overall, I do not recommend Alefeld-Potra-Shi'...


2

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 ...


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$ ...


Only top voted, non community-wiki answers of a minimum length are eligible