This article originated from personal public account: TechFlow, original is not easy, for attention


Today is the seventh article in Thursday’s advanced mathematics project.

Previous articles and we talked about a lot of mathematical theory, today we talk about something useful.

As we all know, many problems in industry are essentially mathematical problems after being abstracted and modeled. When it comes to mathematics, equations are indispensable. In mathematics, we can use all kinds of calculations and formulas, but have we ever thought about how to solve a more complex equation in the field of computer?

If you haven’t thought about it before, you might want to, because it might come up in an interview question later.

dichotomy

The first method we will introduce is dichotomy.

Speaking of dichotomy, you should be familiar with it. To be honest, when I first saw the word dichotomy in an advanced mathematics textbook, I was actually quite shocked. Later, when I saw many other algorithms in statistics and other math books, I became accustomed to them. In the years since I switched to algorithms, I’ve become more and more aware of the importance of mathematics. This doesn’t mean you have to be a math whiz, but if you haven’t graduated yet, it’s worth at least paying attention in math class.

Let’s go back to dichotomy, if you’ve studied dichotomy, this is a very simple algorithm, but if you’ve done LeetCode problem 4, you’ll see that pure dichotomy can be this hard. If we only explain the principle of dichotomy, we will not be able to fully understand the algorithm. To reach this point, I thought long and hard, and finally decided to divide the dichotomy into three levels, modeled after the Zen theory of whether a mountain is a mountain or not.

First is the first level, where we divide one thing in half at a time.

This should be our first and most intuitive idea, like the classic gold coin problem. It says we have several coins, one of which is a gold coin, which is heavier, and the other coins are equal in weight. We only have one scale, how to find the gold coins in the least number of times.


In this problem, we need to keep splitting the coin into two parts and locking the scales to one of them. Find the answer quickly by repeating the above steps.

At the second level, dichotomy is no longer a simple bisection of objects, but a function of halving search. This is the key method to solve the equation.

If I have a function, it increases or decreases on the interval [a, b], and. So we know that the function has to have a solution that is equal to 0, and that we can approximate the solution using dichotomy.


In the picture above,Increasing, and. We went on to get the midpoint of a and B. According to the figure above, we get, so we can putLet’s view it as the new B. So let’s keep looking for a and thetaSince our biggest error is the length of the interval, so when weThe length of the interval is reduced to a sufficiently small size, then it means that we have found a solution that is approximate enough.

In dichotomy, if we don’t do a dichotomy iteration, the interval is cut in half, which is an exponential reduction. So even if the initial interval is very large, after binary iteration, it can be rapidly reduced to a very precise result, and like Taylor series, it can not only get a sufficiently precise value, but also get the range of error.

If we think a little more deeply, we will find that there are some conditions that we can loosen up. For example, do we really need the function to be strictly increasing or decreasing? For example, take a look at this picture:


In the interval b2, b1, the function is not strictly decreasing, but decreasing first and then increasing. But this does not affect the correctness of the result, because in this case, the dichotomy is not by judgmentAnd the value of the function at aThe value of the function is positive or negative. In other words, it just needs to be satisfied, and the function is continuous and equal to 0 point only one, can use the binary search.

Thinking deeply, we enter the third level of dichotomy, which is to drop the limit of increasing and return to the original concept of half-fold.

The essence of dichotomy is to find a space half, and the increasing of a function or the increasing of an element in an array are just appearances, just conditions for us to do half. In other words, if we can find other conditions to cut the search space in half, then we can also get the effect of dichotomy, not just order.

So we’ve come full circle, and we’ve come back to the basic idea of splitting an “object” in two. It is just that we have gone through such a toss and turn, and the original understanding on the surface is the same, but in fact has long been very different.

I did not expect that the algorithm field can also play a Zen, see the mountain is a mountain, see the mountain is not a mountain, finally back to see the mountain or mountain.

Newton iteration method

Now that we’ve done dichotomy, let’s look at another way to find roots quickly, which is the same as dichotomy, which is iterative approximation, but it’s faster. This method was first proposed by Newton, so it’s also known as Newton’s iterative method, and I think when I write Newton’s name out, you can get its components.

The name of Newton’s iterative method looks very bluffing, but the principle is really not difficult. In a word, it is approximated by tangent lines. For example, let’s look at the following figure:


In the figure above, we askThe root of phi, we found one firstO ‘clock, we areI took the derivative of phi to get its tangent line. Obviously, as long as the slope of this tangent line is not zero, then we can definitely find where it intersects the X-axis. So let’s take this intersection as the next value, which is thetaThe point. We repeat the process and iterate, and soon we get a solution close enough.

For the pointThe slope of the tangent line at PI is zeroThe intercept b is zero. The tangent equation is easy to get, which is:


So if we use this equation, we can figure out where it intersects the X-axis, which is thetaValue:


Solve this equation, we can get:


This is the iterative formula of Newton’s method, which is a very good method, much more powerful than the dichotomy method, because it converges faster, and the calculation is not complicated.

To take a look at its power, let’s take a look at an example from the answer of Shihuki Keyoyama [1] :

We useTo findWe all know the value of thetaRange,So let’s figure outThe solution of phi can be found indirectlyThe value of the.

Under this problem, the iteration formula is:


X0 = 3.0 (1)

X1 = 3.1411... (4)

X2 = 3.14159265357... (11),

The x3 = 3.1415926535897932384626433832795020... (34)

X4 = 3.14159265358979323846264338327950288419716939937510582097494459230781640628620899862803482534211706786... (102)

X5 = 3.1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679821480865132823 066470938446095505822317253594081284811174502841027019385211055596446229489549303819644288109756659334461284756482337867 831652712019091456485669234603486104543266482133936072602491412734... (301)

Copy the code

As you can see, in just five iterations, we have calculated PI to over 300 digits. With each iteration, we have improved our accuracy by more than three times, which is quite shocking.

It’s not convergent

However, it is a pity that not all equations can achieve such good results by using Newton’s iterative method, and for some equations, there may even be more and more deviation. Let’s do another example, let’s do an equation. If we plot its iteration, it looks like this:


We can also see this by looking at the iteration formula aboveAs a coefficient, we have thetaSo if you take the derivative of this coefficient, you get the coefficient is zeroIf you look at it, this coefficient is increasing as x increases. In other words, as we iterate, this value gets bigger and bigger, which means we get bigger and bigger amplitudes, which means we get further and further away from convergence.

There are a few cases in which Newton’s iterative method does not converge, but in most cases it works very well. The dichotomy method is fixed to shorten the interval by half each time, while the Newton iteration method is usually more efficient in iteration, and the Newton iteration method can obtain faster convergence speed in general. Compared to dichotomy, Newton’s iterative formula is not difficult to write, and it has applications in machine learning, it is really cheap to learn!

That’s all for today’s article on dichotomy and Newton’s iterative method. If you feel that you have gained something, please click on it. Your effort is very important to me.

The resources

[1]

Zhihu: “https://www.zhihu.com/question/20690553”