4

Even though absolute comparisons may not converge, you should be able to narrow the argument into at least one of several partially overlapping ranges, such that you have a technique that works in that range. For example, you should be able to tell that $x$ definitely falls into at least one of the ranges $A = \left(0,\frac{3}{4}\right]$, $B = \left[\frac{1}{...


2

I think an approach that will work is to "work backwards" through the path, keeping track of the maximum velocity that can be used at that point (subject to the restrictions on acceleration), then "work forwards" along the path, assigning a velocity at each point (subject to the restrictions on acceleration). Represent the path as a ...


2

The Weierstrass Approximation Theorem states that any continuous function can be approximated on a bounded interval $[a, b]$ as closely as desired by a polynomial. In practice, instead of using Taylor series expansions, one uses polynomial minimax approximations $p(x)$ which approximate the function on the chosen interval with the minimal maximum error (thus ...


2

Since you asked specifically about cubic, consider $f(x)=x+x^3$. The Newton iteration would be $$x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)}=x_n-\frac{x_n+x_n^3}{1+3x_n^2}=\frac{2x_n^3}{1+3x_n^2}$$ It converges to the root $x=0$. So, for $1-3|x_n|^2>1/2$, $$\epsilon_{n+1}=|x_{n+1}-0|=\frac{2|x_n|^3}{|1+3x_n^2|}\leq \frac{2|x_n|^3}{1-3|x_n|^2}\leq 4|x_n-0|^3=4\...


2

Let me summarize what I wrote in the comments. It is not a complete answer, since the intervals on which to apply each formula still need to be investigated. It is enough to assume $x\geq0$, since $\cosh(x)$ is even. The type of cancellation that occurs when evaluating, in finite precision floating point (FP2), the expression $$\log(\cosh(x))$$ are: When $x$...


2

Well, this is kind of a numerical method question and it is not related to approximation algorithm. Anyway I think you can search for Bisection method, Newton's method (or Newton-Raphason method), there are of course other ways but this is what I remember from a course in numerical methods. Check this textbook: Steven C. Chapra, and Ryamond P. Canale. ...


2

Have a look at the paper https://www.lirmm.fr/arith18/papers/burgessn-divider.pdf which describes the division / square root hardware implementation in some ARM processors. Roughly the idea: For a division unit, you can look up the initial bits of divisor and dividend in a table to get two bits of result. For double precision with a 53 bit mantissa, you ...


2

This is not an answer, but a response to this comment. Assume that $A$ is the matrix which columns are the rows that we want to test for linear independence. I am putting them are columns for no other reason than personal comfort. Doing the row transformations required in Gaussian elimination correspond to multiplying $A$ from the left by some elementary ...


2

I followed D.W.'s approach and found a solution as follows: In order to use an online derivative calculator, I expressed the cubic spline with points P0, P1, P2 and P3 using variables a through h: P0 = (a, e) P1 = (b, f) P2 = (c, g) P3 = (d, h) The x-y-coordinates and their derivatives are as follows: x(t) = a*(1-t)^3+3*b*(1-t)^2*t+3*c*(1-t)*t^2+d*t^3 x'(...


1

I think there is a mistake in your post: the first equation should be $\ddot{x}(t) = F(t, \dot{x}(t), x(t))$ (and not $\ddot{x}(t + dt)$). Also, in the computation of $kv_i$ and $kx_i$, it should be $kv_i = v(t) + ka_{i-1}\Delta t$ and $kx_i = x(t) + kv_i\Delta t$ (where $\Delta t = dt$ or $\frac{dt}{2}$). $kv_i$ does not use $kv_{i-1}$ (except in the ...


1

It's unclear what $n$ is in your question. If your matrix has dimensions $n \times n$ and your model of computation allows you to perform basic arithmetic operations in constant time then, yes, computing the inverse matrix takes $O(n)$ time.


1

You get a completely different answer if you ask for square roots of n-bit floating point numbers for LARGE n, say n ≥ 1000 or n ≥ 1,000,000. For large n, we usually define the time it takes to multiply two n-bit numbers as M(n). That time depends on how clever our algorithm is; what we learned in school has M(n) = O (n^2), the Karatsuba algorithm has M(n) ≈ ...


1

If you are not a hardware designer, then you likely use the Newton iteration method. Given an equation f(x) = 0, and an approximate solution $x_0$, Newton iteration calculates a (hopefully) better approximation as $x_{n+1} = x_n - f(x_n) / f'(x_n)$. If we change $x = a^{1/2}$ to $x^2 = a$ to $x^2 - a = 0$, then this gives the simple formula $x_{n+1}$ = $x_n -...


1

You can check out the following methods Newton method Heron of Alexandria method Bisection search Exhaustive Enumeration (Terribly slow)


1

I've come to the conclusion that it's not worth doing for my application, so I thought I would post my progress here for anyone else who might be interested in this same problem. My more "proper" solution, which does not put any constraints on the differential equation but instead uses an error estimation for the adaptive steps, more like a ...


1

Assume that due to rounding errors, when you try to calculate the square root of $x^2 + 1$ you actually get the square root plus $\epsilon$ for some small $\epsilon$. Assume that $\epsilon = 10^{-10}$ and $x = 10^{-6}$. Perform the calculations and write down the results.


1

Look at your expression for the error, and extend the base series one more term: If $f''(\xi) = 0$, the convergence is (at least) cubic.


1

There is one method to compare floating point numbers for equality, which is both very simple and correct: You use the equality (==) operator. There is another method to compare whether floating point numbers are identical, which unlike the equality operator would find that -0 and +0 are not the same, and that NaNs with the same bit pattern are the same: Use ...


1

In real problems when the size is large ($n>100000$) the best approach is the numerical solution of the system by an iterative method like GMRES, CG, BiCG, etc. All those algorithms depends strongly on matrix-vector products, so the complexity is as much as $O(n^2)$ which performs better than a direct solution by a LU decomposition with complexity of $O(n^...


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